Dalam gebrakan berani dari tradisi, Kontes Akbar tahun ini akan menampilkan Pertarungan All-Star (All-Star Showdown) khusus: pertandingan eksibisi yang mempertemukan dua skuad elit, Tim Merah (Team Red) dan Tim Biru (Team Blue), dalam duel pemrograman satu lawan satu. Tidak seperti format kontes standar, pertandingan ini mengizinkan ukuran tim yang fleksibel, selama setiap kontestan ditugaskan ke tepat satu tim.

Terdapat $n$ kontestan all-star yang dipilih dari aula kehormatan. Setiap kontestan $i$ dievaluasi di tiga dimensi inti: wawasan algoritmik, kecepatan implementasi, dan ketangguhan debugging. Atribut-atribut ini dikuantifikasi sebagai bilangan bulat positif $(x_i, y_i, z_i)$, membentuk vektor kapabilitas 3D yang menangkap profil kompetitif mereka. Selain itu, setiap kontestan $i$ diberi nilai sinergi bilangan bulat positif $w_i$, yang mencerminkan kemampuan mereka untuk memperkuat performa tim. Nilai tim keseluruhan dari sebuah skuad didefinisikan sebagai hasil kali nilai sinergi dari para anggotanya.

Untuk menjaga integritas kompetitif dan mencegah dominasi oleh kelompok pemrogram dengan gaya serupa, penyelenggara memberlakukan aturan keberagaman yang ketat: di dalam satu tim mana pun, jarak Euclidean antara vektor kapabilitas dari dua anggota mana pun harus setidaknya $d$. Secara formal, untuk setiap dua kontestan berbeda $i$ dan $j$ dalam tim yang sama, harus berlaku $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$. Hal ini memastikan bahwa setiap tim terdiri dari perpaduan pendekatan pemecahan masalah yang seimbang.

Komite penyelenggara ingin menganalisis lanskap kombinatorial dari semua penugasan yang valid. Secara spesifik, untuk setiap bilangan bulat $k = 1, 2, \dots, n - 1$, mereka meminta jumlah nilai Tim Merah di semua partisi valid yang mana Tim Merah berisi tepat $k$ kontestan.

Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.

Masukan

Hanya terdapat satu kasus uji di setiap berkas uji.

Baris pertama berisi dua bilangan bulat $n$ dan $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

Untuk $n$ baris berikutnya, baris ke-$i$ berisi empat bilangan bulat $x_i$, $y_i$, $z_i$, dan $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), yang menyatakan vektor kapabilitas dan nilai sinergi dari kontestan $i$.

Keluaran

Keluarkan $(n - 1)$ baris, di mana baris ke-$i$ berisi sebuah bilangan bulat yang menyatakan jumlah nilai Tim Merah di semua partisi valid yang mana Tim Merah berisi tepat $i$ kontestan modulo $998\,244\,353$.

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

111
1110

Contoh Masukan 2

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

Contoh Keluaran 2

11
1100

Contoh Masukan 3

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

Contoh Keluaran 3

0
0