In a bold departure from tradition, the Grand Contest this year will feature a special All-Star Showdown: a show match pitting two elite squads, Team Red and Team Blue, against each other in a head-to-head programming duel. Unlike the standard contest format, this match allows for flexible team sizes, as long as every contestant is assigned to exactly one team.

There are $n$ all-star contestants selected from the hall of fame. Each contestant $i$ is evaluated across three core dimensions: algorithmic insight, implementation speed, and debugging resilience. These attributes are quantified as positive integers $(x_i, y_i, z_i)$, forming a 3D capability vector that captures their competitive profile. Additionally, each contestant $i$ is assigned a positive integer synergy value $w_i$, reflecting their ability to amplify team performance. The overall team value of a squad is defined as the product of the synergy values of its members.

To maintain competitive integrity and prevent dominance by clusters of stylistically similar coders, the organizers enforce a strict diversity rule: within any single team, the Euclidean distance between the capability vectors of any two members must be at least $d$. Formally, for any two different contestants $i$ and $j$ in the same team, it must hold that $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. This ensures that each team comprises a well-rounded mix of problem-solving approaches.

The organizing committee wishes to analyze the combinatorial landscape of all valid assignments. Specifically, for each integer $k = 1, 2, \dots, n - 1$, they request the sum of the Team Red values over all valid partitions in which Team Red contains exactly $k$ contestants.

Since the answers may be large, output them modulo $998\,244\,353$.

Input

There is only one test case in each test file.

The first line contains two integers $n$ and $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

For the following $n$ lines, the $i$-th line contains four integers $x_i$, $y_i$, $z_i$, and $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), indicating the capability vector and synergy value of contestant $i$.

Output

Output $(n - 1)$ lines, where the $i$-th line contains an integer, indicating the sum of the Team Red values over all valid partitions in which Team Red contains exactly $i$ contestants modulo $998\,244\,353$.

Examples

Sample Input 1

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

Sample Output 1

111
1110

Sample Input 2

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

Sample Output 2

11
1100

Sample Input 3

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

Sample Output 3

0
0