Í djörfu fráviki frá hefðinni mun Stórkeppnin í ár bjóða upp á sérstakt Stjörnueinvígi (All-Star Showdown): sýningarleik þar sem tvö úrvalslið, Rauða liðið (Team Red) og Bláa liðið (Team Blue), mætast í beinu forritunareinvígi. Ólíkt hefðbundnu keppnisfyrirkomulagi leyfir þessi viðureign sveigjanlegar liðsstærðir, svo framarlega sem hver keppandi er settur í nákvæmlega eitt lið.

Valdir hafa verið $n$ stjörnukeppendur úr frægðarhöllinni. Hver keppandi $i$ er metinn á þremur kjarnasviðum: reikniritaskilningi, útfærsluhraða og villuleitarþrautseigju. Þessir eiginleikar eru mældir sem jákvæðar heiltölur $(x_i, y_i, z_i)$ og mynda þrívíðan hæfnivigur sem lýsir keppnisprófíl þeirra. Að auki fær hver keppandi $i$ jákvætt heiltölugildi fyrir samlegð $w_i$, sem endurspeglar getu hans til að efla frammistöðu liðsins. Heildargildi liðs er skilgreint sem margfeldi samlegðargilda liðsmanna þess.

Til að viðhalda heilindum keppninnar og koma í veg fyrir yfirburði hópa forritara með svipaðan stíl framfylgja skipuleggjendur strangri fjölbreytnireglu: innan hvers einstaks liðs verður evklíðsk fjarlægð milli hæfnivigra hvaða tveggja liðsmanna sem er að vera að minnsta kosti $d$. Formlega, fyrir hvaða tvo ólíka keppendur $i$ og $j$ í sama liði verður að gilda að $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Þetta tryggir að hvert lið samanstandi af vel samsettri blöndu af lausnaleiðum.

Skipulagsnefndin óskar eftir því að greina fléttufræðilegt landslag allra gildra skiptinga. Nánar tiltekið, fyrir hverja heiltölu $k = 1, 2, \dots, n - 1$, biðja þeir um summu gilda Rauða liðsins yfir allar gildar skiptingar þar sem Rauða liðið inniheldur nákvæmlega $k$ keppendur.

Þar sem svörin geta verið stór skal prenta þau modulo $998\,244\,353$.

Inntak

Það er aðeins eitt prófunartilvik í hverri prófunarskrá.

Fyrsta línan inniheldur tvær heiltölur $n$ og $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

Í næstu $n$ línum inniheldur $i$-ta línan fjórar heiltölur $x_i$, $y_i$, $z_i$ og $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), sem gefa til kynna hæfnivigur og samlegðargildi keppanda $i$.

Úttak

Prentið $(n - 1)$ línur, þar sem $i$-ta línan inniheldur heiltölu sem gefur til kynna summu gilda Rauða liðsins yfir allar gildar skiptingar þar sem Rauða liðið inniheldur nákvæmlega $i$ keppendur modulo $998\,244\,353$.

Dæmi

Dæmi um inntak 1

3 1
1 1 1 1
1 2 1 10
1 2 3 100

Dæmi um úttak 1

111
1110

Dæmi um inntak 2

3 2
1 1 1 1
1 2 1 10
1 2 3 100

Dæmi um úttak 2

11
1100

Dæmi um inntak 3

3 2
2 1 1 1
1 2 1 10
1 1 2 100

Dæmi um úttak 3

0
0