Trong một bước đột phá táo bạo khỏi truyền thống, Giải đấu Lớn năm nay sẽ có một trận Đại Chiến Siêu Sao (All-Star Showdown) đặc biệt: một trận đấu biểu diễn giữa hai đội tuyển tinh nhuệ, Đội Đỏ (Team Red) và Đội Xanh (Team Blue), đối đầu trực tiếp trong một cuộc đấu lập trình. Không giống như thể thức thi đấu tiêu chuẩn, trận đấu này cho phép quy mô đội linh hoạt, miễn là mỗi thí sinh được phân vào đúng một đội.

Có $n$ thí sinh siêu sao được chọn từ đại sảnh danh vọng. Mỗi thí sinh $i$ được đánh giá qua ba khía cạnh cốt lõi: tư duy thuật toán, tốc độ cài đặt và khả năng gỡ lỗi. Các thuộc tính này được lượng hóa thành các số nguyên dương $(x_i, y_i, z_i)$, tạo thành một vectơ năng lực 3D thể hiện hồ sơ thi đấu của họ. Ngoài ra, mỗi thí sinh $i$ được gán một giá trị cộng hưởng nguyên dương $w_i$, phản ánh khả năng khuếch đại hiệu suất toàn đội của họ. Tổng giá trị đội của một đội tuyển được định nghĩa là tích các giá trị cộng hưởng của các thành viên trong đội.

Để duy trì tính công bằng trong thi đấu và ngăn chặn sự thống trị của các nhóm lập trình viên có phong cách tương tự nhau, ban tổ chức áp dụng một quy tắc đa dạng nghiêm ngặt: trong bất kỳ một đội nào, khoảng cách Euclid giữa các vectơ năng lực của hai thành viên bất kỳ phải ít nhất là $d$. Một cách hình thức, với hai thí sinh khác nhau bất kỳ $i$ và $j$ trong cùng một đội, điều kiện $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$ phải được thỏa mãn. Điều này đảm bảo rằng mỗi đội bao gồm sự kết hợp toàn diện của các phương pháp giải quyết vấn đề.

Ban tổ chức muốn phân tích bức tranh tổ hợp của tất cả các cách phân chia hợp lệ. Cụ thể, với mỗi số nguyên $k = 1, 2, \dots, n - 1$, họ yêu cầu tính tổng giá trị của Đội Đỏ trên tất cả các cách phân hoạch hợp lệ mà trong đó Đội Đỏ chứa đúng $k$ thí sinh.

Vì kết quả có thể rất lớn, hãy in ra phần dư của chúng khi chia cho $998\,244\,353$.

Dữ liệu vào

Chỉ có một bộ dữ liệu trong mỗi tệp dữ liệu.

Dòng đầu tiên chứa hai số nguyên $n$ và $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$).

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa bốn số nguyên $x_i$, $y_i$, $z_i$ và $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$), cho biết vectơ năng lực và giá trị cộng hưởng của thí sinh $i$.

Kết quả

In ra $(n - 1)$ dòng, trong đó dòng thứ $i$ chứa một số nguyên cho biết tổng giá trị của Đội Đỏ trên tất cả các cách phân hoạch hợp lệ mà Đội Đỏ chứa đúng $i$ thí sinh, lấy phần dư theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu mẫu 1

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

Kết quả mẫu 1

111
1110

Dữ liệu mẫu 2

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

Kết quả mẫu 2

11
1100

Dữ liệu mẫu 3

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

Kết quả mẫu 3

0
0