I et dristig brudd med tradisjonen vil årets store konkurranse by på et spesielt All-Star-oppgjør (All-Star Showdown): en oppvisningskamp der to elitelag, Lag Rød (Team Red) og Lag Blå (Team Blue), møtes til en direkte programmeringsduell. I motsetning til standardformatet tillater denne kampen fleksible lagstørrelser, så lenge hver deltaker tildeles nøyaktig ett lag.

Det er $n$ all-star-deltakere valgt ut fra æresgalleriet. Hver deltaker $i$ vurderes langs tre kjernedimensjoner: algoritmisk innsikt, implementasjonshastighet og feilsøkingsutholdenhet. Disse egenskapene kvantifiseres som positive heltall $(x_i, y_i, z_i)$, og danner en 3D-kapasitetsvektor som fanger opp konkurranseprofilen deres. I tillegg tildeles hver deltaker $i$ en positiv heltalls synergiverdi $w_i$, som gjenspeiler evnen deres til å forsterke lagets prestasjoner. Den totale lagverdien til et lag er definert som produktet av synergiverdiene til medlemmene.

For å opprettholde konkurransens integritet og forhindre dominans fra klynger av stilistisk like programmerere, håndhever arrangørene en streng mangfoldsregel: innenfor ethvert enkelt lag må den euklidske avstanden mellom kapasitetsvektorene til to vilkårlige medlemmer være minst $d$. Formelt må det for enhver to forskjellige deltakere $i$ og $j$ på samme lag gjelde at $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Dette sikrer at hvert lag består av en velbalansert blanding av problemløsningstilnærminger.

Organisasjonskomiteen ønsker å analysere det kombinatoriske landskapet for alle gyldige tildelinger. Spesifikt, for hvert heltall $k = 1, 2, \dots, n - 1$, ber de om summen av Lag Røds verdier over alle gyldige partisjoner der Lag Rød inneholder nøyaktig $k$ deltakere.

Siden svarene kan være store, skal du skrive dem ut modulo $998\,244\,353$.

Inndata

Det er bare ett testtilfelle i hver testfil.

Den første linjen inneholder to heltall $n$ og $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

På de følgende $n$ linjene inneholder den $i$-te linjen fire heltall $x_i$, $y_i$, $z_i$ og $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), som angir kapasitetsvektoren og synergiverdien til deltaker $i$.

Utdata

Skriv ut $(n - 1)$ linjer, der den $i$-te linjen inneholder et heltall som angir summen av Lag Røds verdier over alle gyldige partisjoner der Lag Rød inneholder nøyaktig $i$ deltakere modulo $998\,244\,353$.

Eksempler

Eksempelinndata 1

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

Eksempelutdata 1

111
1110

Eksempelinndata 2

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

Eksempelutdata 2

11
1100

Eksempelinndata 3

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

Eksempelutdata 3

0
0