W śmiałym odejściu od tradycji, tegoroczny Wielki Konkurs obejmie specjalne Starcie Gwiazd (All-Star Showdown): mecz pokazowy, w którym dwie elitarne drużyny, Drużyna Czerwona (Team Red) i Drużyna Niebieska (Team Blue), zmierzą się w bezpośrednim pojedynku programistycznym. W przeciwieństwie do standardowego formatu zawodów, ten mecz pozwala na elastyczne rozmiary drużyn, o ile każdy uczestnik zostanie przypisany do dokładnie jednej drużyny.

Wybrano $n$ gwiazdorskich uczestników z galerii sław. Każdy uczestnik $i$ jest oceniany w trzech kluczowych wymiarach: intuicji algorytmicznej, szybkości implementacji oraz wytrwałości w debugowaniu. Cechy te są wyrażone jako dodatnie liczby całkowite $(x_i, y_i, z_i)$, tworzące trójwymiarowy wektor umiejętności opisujący profil zawodnika. Ponadto każdemu uczestnikowi $i$ przypisano dodatnią całkowitą wartość synergii $w_i$, odzwierciedlającą jego zdolność do wzmacniania wyników zespołu. Całkowita wartość drużyny jest zdefiniowana jako iloczyn wartości synergii jej członków.

Aby zachować uczciwość rywalizacji i zapobiec dominacji grup podobnie piszących koderów, organizatorzy wprowadzili ścisłą zasadę różnorodności: w obrębie dowolnej jednej drużyny odległość euklidesowa między wektorami umiejętności dowolnych dwóch członków musi wynosić co najmniej $d$. Formalnie, dla dowolnych dwóch różnych uczestników $i$ oraz $j$ w tej samej drużynie musi zachodzić warunek $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Gwarantuje to, że każda drużyna składa się ze zrównoważonej mieszanki podejść do rozwiązywania problemów.

Komitet organizacyjny chce przeanalizować kombinatoryczny krajobraz wszystkich poprawnych przydziałów. Dokładniej, dla każdej liczby całkowitej $k = 1, 2, \dots, n - 1$ prosi o wyznaczenie sumy wartości Drużyny Czerwonej po wszystkich poprawnych podziałach, w których Drużyna Czerwona liczy dokładnie $k$ uczestników.

Ponieważ odpowiedzi mogą być duże, wypisz je modulo $998\,244\,353$.

Wejście

W każdym pliku testowym znajduje się tylko jeden przypadek testowy.

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

W kolejnych $n$ wierszach $i$-ty wiersz zawiera cztery liczby całkowite $x_i$, $y_i$, $z_i$ oraz $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), oznaczające wektor umiejętności i wartość synergii uczestnika $i$.

Wyjście

Wypisz $(n - 1)$ wierszy, gdzie $i$-ty wiersz zawiera jedną liczbę całkowitą oznaczającą sumę wartości Drużyny Czerwonej po wszystkich poprawnych podziałach, w których Drużyna Czerwona zawiera dokładnie $i$ uczestników, modulo $998\,244\,353$.

Przykłady

Przykładowe wejście 1

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

Przykładowe wyjście 1

111
1110

Przykładowe wejście 2

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

Przykładowe wyjście 2

11
1100

Przykładowe wejście 3

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

Przykładowe wyjście 3

0
0