Con un audace distacco dalla tradizione, il Gran Concorso di quest'anno presenterà una speciale Sfida All-Star (All-Star Showdown): un match d'esibizione che metterà di fronte due squadre d'élite, la Squadra Rossa (Team Red) e la Squadra Blu (Team Blue), in un duello di programmazione testa a testa. A differenza del formato standard del concorso, questa sfida consente dimensioni flessibili per le squadre, purché ogni concorrente sia assegnato esattamente a una squadra.

Ci sono $n$ concorrenti all-star selezionati dalla hall of fame. Ogni concorrente $i$ viene valutato lungo tre dimensioni fondamentali: intuizione algoritmica, velocità di implementazione e resilienza nel debugging. Questi attributi sono quantificati come interi positivi $(x_i, y_i, z_i)$, formando un vettore di capacità 3D che cattura il loro profilo competitivo. Inoltre, a ogni concorrente $i$ viene assegnato un valore di sinergia intero positivo $w_i$, che riflette la sua capacità di amplificare le prestazioni della squadra. Il valore complessivo di una squadra è definito come il prodotto dei valori di sinergia dei suoi membri.

Per mantenere l'integrità competitiva e prevenire il dominio di gruppi di programmatori stilisticamente simili, gli organizzatori impongono una rigorosa regola sulla diversità: all'interno di qualsiasi singola squadra, la distanza euclidea tra i vettori di capacità di due membri qualsiasi deve essere almeno $d$. Formalmente, per qualsiasi coppia di concorrenti diversi $i$ e $j$ nella stessa squadra, deve valere $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Ciò garantisce che ogni squadra comprenda un mix equilibrato di approcci alla risoluzione dei problemi.

Il comitato organizzatore desidera analizzare il panorama combinatorio di tutte le assegnazioni valide. Nello specifico, per ogni intero $k = 1, 2, \dots, n - 1$, richiede la somma dei valori della Squadra Rossa su tutte le partizioni valide in cui la Squadra Rossa contiene esattamente $k$ concorrenti.

Poiché le risposte possono essere grandi, stampale modulo $998\,244\,353$.

Input

C'è un solo caso di test in ciascun file di test.

La prima riga contiene due interi $n$ e $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

Nelle successive $n$ righe, la $i$-esima riga contiene quattro interi $x_i$, $y_i$, $z_i$ e $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), che indicano il vettore di capacità e il valore di sinergia del concorrente $i$.

Output

Stampa $(n - 1)$ righe, dove la $i$-esima riga contiene un intero che indica la somma dei valori della Squadra Rossa su tutte le partizioni valide in cui la Squadra Rossa contiene esattamente $i$ concorrenti modulo $998\,244\,353$.

Esempi

Input di esempio 1

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

Output di esempio 1

111
1110

Input di esempio 2

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

Output di esempio 2

11
1100

Input di esempio 3

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

Output di esempio 3

0
0