伝統を大胆に打ち破り、今年のグランドコンテストでは特別企画「オールスター対決（All-Star Showdown）」が開催されます。これは、Team Red と Team Blue という 2 つのエリート部隊が真っ向からぶつかり合うプログラミング対決です。通常のコンテスト形式とは異なり、この試合ではすべての競技者がちょうど 1 つのチームに割り当てられていれば、チームの人数を自由に決めることができます。

殿堂入りメンバーから選ばれた $n$ 人のオールスター競技者がいます。各競技者 $i$ は、アルゴリズムの洞察力、実装スピード、デバッグの粘り強さという 3 つの核心的な次元で評価されます。これらの属性は正の整数 $(x_i, y_i, z_i)$ として定量化され、競争力を捉える 3 次元の能力ベクトルを形成します。さらに、各競技者 $i$ にはチームのパフォーマンスを増幅する能力を反映した正の整数のシナジー値 $w_i$ が割り当てられます。チームの総合価値は、そのメンバーのシナジー値の積として定義されます。

競技の公平性を保ち、似たスタイルのコーダー集団による独占を防ぐため、主催者は厳格な多様性ルールを課しています。同一チーム内の任意の 2 人のメンバーの能力ベクトル間のユークリッド距離は $d$ 以上でなければなりません。形式的には、同じチームに属する任意の異なる 2 人の競技者 $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$ について、Team Red にちょうど $k$ 人の競技者が含まれるようなすべての有効な分割における Team Red の総合価値の総和を求めています。

答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

各テストファイルには 1 つのテストケースのみが含まれます。

1 行目には 2 つの整数 $n$ と $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$) が与えられます。

続く $n$ 行のうち $i$ 行目には、競技者 $i$ の能力ベクトルとシナジー値を表す 4 つの整数 $x_i$, $y_i$, $z_i$, $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$) が与えられます。

出力

$(n - 1)$ 行出力してください。$i$ 行目には、Team Red にちょうど $i$ 人の競技者が含まれるようなすべての有効な分割における Team Red の総合価値の総和を $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