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