為了打破傳統，今年的大賽將舉辦一場特別的「全明星對決」（All-Star Showdown）：一場由兩支精英隊伍——紅隊（Team Red）和藍隊（Team Blue）——進行的正面程式設計對決。與標準比賽形式不同，本次比賽允許靈活的隊伍規模，只要每位參賽者都被分配到且僅被分配到一支隊伍中即可。

共有 $n$ 名從名人堂中選出的全明星參賽者。每位參賽者 $i$ 在三個核心維度上進行評估：演算法洞察力、實作速度和除錯韌性。這些屬性被量化為正整數 $(x_i, y_i, z_i)$，形成一個捕捉其競爭特徵的 3D 能力向量。此外，每位參賽者 $i$ 都被分配了一個正整數協同值 $w_i$，反映了他們提升團隊表現的能力。一支隊伍的整體團隊價值定義為其成員協同值的乘積。

為了保持競爭的公平性並防止風格相似的程式設計師群體佔據主導地位，組織者強制執行一項嚴格的多樣性規則：在任何單一隊伍內，任意兩名成員能力向量之間的歐幾里得距離必須至少為 $d$。形式上，對於同一隊伍中的任意兩名不同參賽者 $i$ 和 $j$，必須滿足 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$。這確保了每支隊伍都由解決問題的方法論的均衡組合構成。

組委會希望分析所有有效分配的組合景觀。具體而言，對於每個整數 $k = 1, 2, \dots, n - 1$，他們要求計算在所有紅隊恰好包含 $k$ 名參賽者的有效劃分中，紅隊價值的總和。

由於答案可能很大，請將結果對 $998\,244\,353$ 取模。

輸入格式

每個測試檔案中僅包含一組測試資料。

第一行包含兩個整數 $n$ 和 $d$（$2 \le n \le 10^5$，$1 \le d \le 10^8$）。

接下來的 $n$ 行中，第 $i$ 行包含四個整數 $x_i$、$y_i$、$z_i$ 和 $w_i$（$1 \le x_i, y_i, z_i, w_i \le 10^8$），分別表示參賽者 $i$ 的能力向量和協同值。

輸出格式

輸出 $(n - 1)$ 行，其中第 $i$ 行包含一個整數，表示在紅隊恰好包含 $i$ 名參賽者的所有有效劃分中，紅隊價值的總和對 $998\,244\,353$ 取模的結果。

範例

範例輸入 1

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

範例輸出 1

111
1110

範例輸入 2

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

範例輸出 2

11
1100

範例輸入 3

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

範例輸出 3

0
0