В качестве смелого отступления от традиций в этом году на Гранд-контесте пройдёт специальная «Битва всех звёзд» (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