ในการฉีกกรอบประเพณีอย่างกล้าหาญ การแข่งขันใหญ่ในปีนี้จะมีการแข่งขันพิเศษ All-Star Showdown ซึ่งเป็นการแข่งขันโชว์แมตช์ระหว่างสองทีมชั้นยอด ได้แก่ Team Red และ Team Blue ในการดวลเขียนโปรแกรมแบบตัวต่อตัว ต่างจากรูปแบบการแข่งขันมาตรฐาน แมตช์นี้อนุญาตให้ขนาดทีมมีความยืดหยุ่นได้ ตราบใดที่ผู้เข้าแข่งขันแต่ละคนถูกจัดให้อยู่ในทีมเดียวเท่านั้น

มีผู้เข้าแข่งขันออลสตาร์ $n$ คนที่ได้รับเลือกจากหอเกียรติยศ ผู้เข้าแข่งขันแต่ละคน $i$ จะได้รับการประเมินในสามมิติหลัก ได้แก่ ความเข้าใจเชิงอัลกอริทึม ความเร็วในการเขียนโค้ด และความยืดหยุ่นในการดีบัก คุณลักษณะเหล่านี้ถูกวัดค่าเป็นจำนวนเต็มบวก $(x_i, y_i, z_i)$ ซึ่งก่อตัวเป็นเวกเตอร์ความสามารถ 3 มิติที่แสดงถึงโปรไฟล์การแข่งขันของพวกเขา นอกจากนี้ ผู้เข้าแข่งขันแต่ละคน $i$ ยังได้รับค่าความสอดคล้อง (synergy) เป็นจำนวนเต็มบวก $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$ พวกเขาต้องการทราบผลรวมของมูลค่าของ Team Red จากการแบ่งกลุ่มที่ถูกต้องทั้งหมดซึ่ง Team Red มีผู้เข้าแข่งขันอยู่ $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$ ประกอบด้วยจำนวนเต็มหนึ่งตัว แสดงถึงผลรวมของมูลค่าของ Team Red จากการแบ่งกลุ่มที่ถูกต้องทั้งหมดซึ่ง Team Red มีผู้เข้าแข่งขันอยู่ $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