في خروج جريء عن التقاليد، ستشهد المسابقة الكبرى هذا العام مواجهة خاصة لكل النجوم (All-Star Showdown): مباراة استعراضية تجمع بين فريقين من النخبة، الفريق الأحمر (Team Red) والفريق الأزرق (Team Blue)، في مبارزة برمجية وجهاً لوجه. على عكس نظام المسابقة القياسي، تسمح هذه المباراة بأحجام فرق مرنة، طالما يتم تعيين كل متسابق في فريق واحد بالضبط.

هناك $n$ من المتسابقين النجوم المختارين من قاعة المشاهير. يتم تقييم كل متسابق $i$ عبر ثلاثة أبعاد أساسية: البصيرة الخوارزمية، وسرعة التنفيذ، والمرونة في تصحيح الأخطاء. يتم تحديد هذه السمات كأعداد صحيحة موجبة $(x_i, y_i, z_i)$، مما يشكل متجه قدرات ثلاثي الأبعاد يلتقط ملفهم التنافسي. بالإضافة إلى ذلك، يتم إعطاء كل متسابق $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