Rohkeana poikkeamana perinteestä tämän vuoden suurkisan ohjelmassa on erityinen All-Star-välienselvittely (All-Star Showdown): näytösottelu, jossa kaksi eliittijoukkuetta, Punainen joukkue (Team Red) ja Sininen joukkue (Team Blue), kohtaavat suorassa ohjelmointikaksinkamppailussa. Tavallisesta kilpailumuodosta poiketen tässä ottelussa joukkueiden koot ovat joustavia, kunhan jokainen kilpailija sijoitetaan täsmälleen yhteen joukkueeseen.

Kunniagalleriasta on valittu $n$ all-star-kilpailijaa. Jokainen kilpailija $i$ arvioidaan kolmella ydinulottuvuudella: algoritminen oivalluskyky, toteutusnopeus ja virheenkorjauskestävyys. Nämä ominaisuudet esitetään positiivisina kokonaislukuina $(x_i, y_i, z_i)$, jotka muodostavat kilpailijan profiilia kuvaavan kolmiulotteisen kykyvektorin. Lisäksi jokaiselle kilpailijalle $i$ on annettu positiivinen kokonaislukuarvoinen synergia-arvo $w_i$, joka kuvaa hänen kykyään vahvistaa joukkueen suoritusta. Joukkueen kokonaisarvo määritellään sen jäsenten synergia-arvojen tulona.

Kilpailun reiluuden säilyttämiseksi ja tyyliltään samankaltaisten ohjelmoijien ryhmittymien ylivoiman estämiseksi järjestäjät asettavat tiukan monimuotoisuussäännön: minkä tahansa yksittäisen joukkueen sisällä kenen tahansa kahden jäsenen kykyvektorien välisen euklidisen etäisyyden on oltava vähintään $d$. Muodollisesti kaikille samassa joukkueessa oleville eri kilpailijoille $i$ ja $j$ on pädettävä $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Tämä varmistaa, että jokainen joukkue koostuu monipuolisesta yhdistelmästä ongelmanratkaisutapoja.

Järjestelytoimikunta haluaa analysoida kaikkien kelvollisten jakoehdotusten kombinatorista rakennetta. Tarkemmin sanottuna jokaiselle kokonaisluvulle $k = 1, 2, \dots, n - 1$ he haluavat Punaisen joukkueen arvojen summan yli kaikkien kelvollisten ositusten, joissa Punaisessa joukkueessa on täsmälleen $k$ kilpailijaa.

Koska vastaukset voivat olla suuria, tulosta ne modulo $998\,244\,353$.

Syöte

Jokaisessa testitiedostossa on vain yksi testitapaus.

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

Seuraavilla $n$ rivillä $i$:s rivi sisältää neljä kokonaislukua $x_i$, $y_i$, $z_i$ ja $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), jotka ilmaisevat kilpailijan $i$ kykyvektorin ja synergia-arvon.

Tuloste

Tulosta $(n - 1)$ riviä, missä $i$:s rivi sisältää kokonaisluvun, joka ilmaisee Punaisen joukkueen arvojen summan yli kaikkien kelvollisten ositusten, joissa Punaisessa joukkueessa on täsmälleen $i$ kilpailijaa, modulo $998\,244\,353$.

Esimerkit

Esimerkkisyöte 1

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

Esimerkkituloste 1

111
1110

Esimerkkisyöte 2

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

Esimerkkituloste 2

11
1100

Esimerkkisyöte 3

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

Esimerkkituloste 3

0
0