I ett djärvt avsteg från traditionen kommer årets stora tävling att bjuda på en speciell All-Star-uppgörelse (All-Star Showdown): en uppvisningsmatch där två elittrupper, Lag Röd (Team Red) och Lag Blå (Team Blue), ställs mot varandra i en direkt programmeringsduell. Till skillnad från standardformatet tillåter denna match flexibla lagstorlekar, så länge varje tävlande tilldelas exakt ett lag.

Det finns $n$ all-star-tävlande utvalda från hall of fame. Varje tävlande $i$ utvärderas i tre kärndimensioner: algoritmisk insikt, implementationshastighet och felsökningsuthållighet. Dessa attribut kvantifieras som positiva heltal $(x_i, y_i, z_i)$ och bildar en 3D-kapacitetsvektor som fångar deras tävlingsprofil. Dessutom tilldelas varje tävlande $i$ ett positivt heltalsvärde för synergi $w_i$, vilket speglar deras förmåga att förstärka lagets prestation. Det totala lagvärdet för en trupp definieras som produkten av synergivärdena för dess medlemmar.

För att upprätthålla tävlingsintegriteten och förhindra dominans av kluster av stilistiskt liknande programmerare tillämpar arrangörerna en strikt mångfaldsregel: inom varje enskilt lag måste det euklidiska avståndet mellan kapacitetsvektorerna för två godtyckliga medlemmar vara minst $d$. Formellt måste det för varje par av olika tävlande $i$ och $j$ i samma lag gälla att $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Detta säkerställer att varje lag består av en väl avvägd blandning av problemlösningsmetoder.

Organisationskommittén vill analysera det kombinatoriska landskapet av alla giltiga tilldelningar. Specifikt, för varje heltal $k = 1, 2, \dots, n - 1$, efterfrågar de summan av Lag Röds värden över alla giltiga partitioner där Lag Röd innehåller exakt $k$ tävlande.

Eftersom svaren kan vara stora ska de skrivas ut modulo $998\,244\,353$.

Indata

Det finns bara ett testfall i varje testfil.

Den första raden innehåller två heltal $n$ och $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

På de följande $n$ raderna innehåller den $i$-te raden fyra heltal $x_i$, $y_i$, $z_i$ och $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), som anger kapacitetsvektorn och synergivärdet för tävlande $i$.

Utdata

Skriv ut $(n - 1)$ rader, där den $i$-te raden innehåller ett heltal som anger summan av Lag Röds värden över alla giltiga partitioner där Lag Röd innehåller exakt $i$ tävlande modulo $998\,244\,353$.

Exempel

Exempelindata 1

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

Exempelutdata 1

111
1110

Exempelindata 2

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

Exempelutdata 2

11
1100

Exempelindata 3

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

Exempelutdata 3

0
0