Дәстүрден батыл түрде ауытқып, биылғы Үлкен жарыста арнайы «Жұлдыздар шайқасы» (All-Star Showdown) өтеді: бұл екі элиталық құрама — Қызыл команда (Team Red) мен Көк команда (Team Blue) — бетпе-бет бағдарламалау дуэлінде кездесетін көрсетілім матчы. Стандартты жарыс форматынан айырмашылығы, бұл матчта әрбір қатысушы дәл бір командаға бөлінсе болғаны, команда өлшемдері еркін бола алады.

Даңқ залынан таңдалған $n$ жұлдызды қатысушы бар. Әрбір $i$ қатысушысы үш негізгі өлшем бойынша бағаланады: алгоритмдік түйсік, іске асыру жылдамдығы және жөндеуге (дебагқа) төзімділік. Бұл сипаттамалар олардың жарыстық бейінін сипаттайтын 3D қабілет векторын құрайтын оң бүтін $(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$-ші жолында $i$ қатысушысының қабілет векторы мен синергия мәнін білдіретін төрт бүтін $x_i$, $y_i$, $z_i$ және $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$) сандары берілген.

Шығыс деректері

$(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