Rompant audacieusement avec la tradition, le Grand Concours de cette année proposera une Confrontation All-Star spéciale : un match de gala opposant deux équipes d'élite, l'Équipe Rouge (Team Red) et l'Équipe Bleue (Team Blue), dans un duel de programmation en face-à-face. Contrairement au format de concours standard, ce match permet des tailles d'équipe flexibles, tant que chaque participant est affecté à exactement une équipe.

Il y a $n$ participants all-star sélectionnés au panthéon de la gloire. Chaque participant $i$ est évalué selon trois dimensions fondamentales : l'intuition algorithmique, la vitesse d'implémentation et la résilience au débogage. Ces attributs sont quantifiés sous forme d'entiers strictement positifs $(x_i, y_i, z_i)$, formant un vecteur de capacités 3D qui résume leur profil compétitif. De plus, chaque participant $i$ se voit attribuer une valeur de synergie entière strictement positive $w_i$, reflétant sa capacité à amplifier les performances de l'équipe. La valeur globale d'une équipe est définie comme le produit des valeurs de synergie de ses membres.

Pour préserver l'intégrité de la compétition et éviter la domination de groupes de programmeurs au style similaire, les organisateurs imposent une règle stricte de diversité : au sein d'une même équipe, la distance euclidienne entre les vecteurs de capacités de deux membres quelconques doit être d'au moins $d$. Formellement, pour deux participants différents quelconques $i$ et $j$ de la même équipe, on doit avoir $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Cela garantit que chaque équipe est composée d'un mélange équilibré d'approches de résolution de problèmes.

Le comité d'organisation souhaite analyser le paysage combinatoire de toutes les affectations valides. Plus précisément, pour chaque entier $k = 1, 2, \dots, n - 1$, il demande la somme des valeurs de l'Équipe Rouge sur toutes les partitions valides dans lesquelles l'Équipe Rouge contient exactement $k$ participants.

Comme les réponses peuvent être grandes, affichez-les modulo $998\,244\,353$.

Entrée

Il n'y a qu'un seul cas de test dans chaque fichier de test.

La première ligne contient deux entiers $n$ et $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

Pour les $n$ lignes suivantes, la $i$-ème ligne contient quatre entiers $x_i$, $y_i$, $z_i$ et $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), indiquant le vecteur de capacités et la valeur de synergie du participant $i$.

Sortie

Affichez $(n - 1)$ lignes, où la $i$-ème ligne contient un entier indiquant la somme des valeurs de l'Équipe Rouge sur toutes les partitions valides dans lesquelles l'Équipe Rouge contient exactement $i$ participants, modulo $998\,244\,353$.

Exemples

Entrée d'exemple 1

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

Sortie d'exemple 1

111
1110

Entrée d'exemple 2

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

Sortie d'exemple 2

11
1100

Entrée d'exemple 3

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

Sortie d'exemple 3

0
0