בחריגה נועזת מהמסורת, התחרות הגדולה השנה תכלול עימות אול-סטארס (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