En una audaz ruptura con la tradición, el Gran Concurso de este año contará con un Duelo de Estrellas (All-Star Showdown) especial: una partida de exhibición que enfrentará a dos escuadrones de élite, el Equipo Rojo (Team Red) y el Equipo Azul (Team Blue), en un duelo de programación cara a cara. A diferencia del formato de concurso estándar, este encuentro permite tamaños de equipo flexibles, siempre que cada concursante sea asignado a exactamente un equipo.

Hay $n$ concursantes estrella seleccionados del salón de la fama. Cada concursante $i$ es evaluado en tres dimensiones fundamentales: intuición algorítmica, velocidad de implementación y resiliencia en la depuración. Estos atributos se cuantifican como enteros positivos $(x_i, y_i, z_i)$, formando un vector de capacidad 3D que captura su perfil competitivo. Además, a cada concursante $i$ se le asigna un valor de sinergia entero positivo $w_i$, que refleja su capacidad para amplificar el rendimiento del equipo. El valor total de un equipo se define como el producto de los valores de sinergia de sus miembros.

Para mantener la integridad competitiva y evitar el dominio de grupos de programadores con estilos similares, los organizadores imponen una estricta regla de diversidad: dentro de cualquier equipo individual, la distancia euclidiana entre los vectores de capacidad de cualesquiera dos miembros debe ser de al menos $d$. Formalmente, para cualesquiera dos concursantes diferentes $i$ y $j$ en el mismo equipo, debe cumplirse que $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Esto asegura que cada equipo comprenda una combinación equilibrada de enfoques de resolución de problemas.

El comité organizador desea analizar el panorama combinatorio de todas las asignaciones válidas. Específicamente, para cada entero $k = 1, 2, \dots, n - 1$, solicitan la suma de los valores del Equipo Rojo sobre todas las particiones válidas en las que el Equipo Rojo contiene exactamente $k$ concursantes.

Como las respuestas pueden ser grandes, imprímelas módulo $998\,244\,353$.

Entrada

Solo hay un caso de prueba en cada archivo de prueba.

La primera línea contiene dos enteros $n$ y $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

En las siguientes $n$ líneas, la $i$-ésima línea contiene cuatro enteros $x_i$, $y_i$, $z_i$ y $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), que indican el vector de capacidad y el valor de sinergia del concursante $i$.

Salida

Imprime $(n - 1)$ líneas, donde la $i$-ésima línea contiene un entero que indica la suma de los valores del Equipo Rojo sobre todas las particiones válidas en las que el Equipo Rojo contiene exactamente $i$ concursantes, módulo $998\,244\,353$.

Ejemplos

Entrada de ejemplo 1

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

Salida de ejemplo 1

111
1110

Entrada de ejemplo 2

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

Salida de ejemplo 2

11
1100

Entrada de ejemplo 3

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

Salida de ejemplo 3

0
0