In einer mutigen Abkehr von der Tradition bietet der große Wettbewerb in diesem Jahr einen besonderen All-Star-Showdown: ein Showmatch, bei dem zwei Elitetrupps, Team Rot (Team Red) und Team Blau (Team Blue), in einem direkten Programmierduell gegeneinander antreten. Anders als beim Standardformat erlaubt dieses Match flexible Teamgrößen, solange jeder Teilnehmer genau einem Team zugewiesen wird.

Es gibt $n$ All-Star-Teilnehmer, die aus der Ruhmeshalle ausgewählt wurden. Jeder Teilnehmer $i$ wird in drei Kerndimensionen bewertet: algorithmisches Verständnis, Implementierungsgeschwindigkeit und Debugging-Belastbarkeit. Diese Attribute werden als positive ganze Zahlen $(x_i, y_i, z_i)$ quantifiziert und bilden einen 3D-Fähigkeitsvektor, der ihr Wettbewerbsprofil erfasst. Zusätzlich wird jedem Teilnehmer $i$ ein positiver ganzzahliger Synergiewert $w_i$ zugewiesen, der seine Fähigkeit widerspiegelt, die Teamleistung zu verstärken. Der Gesamtwert eines Teams ist definiert als das Produkt der Synergiewerte seiner Mitglieder.

Um die Integrität des Wettbewerbs zu wahren und eine Dominanz durch Gruppen stilistisch ähnlicher Programmierer zu verhindern, setzen die Organisatoren eine strenge Diversitätsregel durch: Innerhalb jedes einzelnen Teams muss der euklidische Abstand zwischen den Fähigkeitsvektoren zweier beliebiger Mitglieder mindestens $d$ betragen. Formal muss für zwei beliebige verschiedene Teilnehmer $i$ und $j$ im selben Team gelten, dass $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Dies stellt sicher, dass jedes Team aus einer ausgewogenen Mischung von Problemlösungsansätzen besteht.

Das Organisationskomitee möchte die kombinatorische Landschaft aller gültigen Zuweisungen analysieren. Insbesondere bittet es für jede ganze Zahl $k = 1, 2, \dots, n - 1$ um die Summe der Werte von Team Rot über alle gültigen Partitionen, in denen Team Rot genau $k$ Teilnehmer enthält.

Da die Antworten groß sein können, geben Sie diese modulo $998\,244\,353$ aus.

Eingabe

In jeder Testdatei gibt es nur einen Testfall.

Die erste Zeile enthält zwei ganze Zahlen $n$ und $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

In den folgenden $n$ Zeilen enthält die $i$-te Zeile vier ganze Zahlen $x_i$, $y_i$, $z_i$ und $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), die den Fähigkeitsvektor und den Synergiewert von Teilnehmer $i$ angeben.

Ausgabe

Geben Sie $(n - 1)$ Zeilen aus, wobei die $i$-te Zeile eine ganze Zahl enthält, die die Summe der Werte von Team Rot über alle gültigen Partitionen angibt, in denen Team Rot genau $i$ Teilnehmer enthält, modulo $998\,244\,353$.

Beispiele

Beispieleingabe 1

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

Beispielausgabe 1

111
1110

Beispieleingabe 2

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

Beispielausgabe 2

11
1100

Beispieleingabe 3

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

Beispielausgabe 3

0
0