為咗打破傳統，今年嘅大賽將舉辦一場特別嘅「全明星對決」（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