問題文

魔法使いのコアさんは、$1, 2, \dots, N$ の番号がついた $N$ 体のモンスターと戦っています。
モンスター $i$ $(1 \leq i \leq N)$ は二次元平面上の座標 $(X_{i}, Y_{i})$ に位置し、体力は $H_{i}$ です。

コアさんは二次元平面上の座標を自由に一つ選び、爆裂魔法を使用します。

座標 $(x,y)$ で爆裂魔法を使用したとき、任意のモンスター $i$ $(1 \leq i \leq N)$ について、その体力を $d_{i}$ だけ減らせます。
ここで、$d_{i} = \max( M - |x - X_{i}| - |y - Y_{i}|, 0 )$ です。

$i = 1,2,\dots,N$ の順に、次の問いに答えてください。

• 二次元平面上において、次の条件を満たす点 $(x,y)$ からなる領域の面積を $\mathrm{mod} \ 998244353$ で求めよ。

• コアさんが座標 $(x, y)$ で爆裂魔法を使用したとき、$N$ 体のモンスターのうちちょうど $i$ 体の体力が $0$ 以下になる

注記

本問の制約下において、求める面積は有理数であることが保証されます。

これを既約分数 $p / q$ と表したとき、$p \equiv q \times r \pmod{998244353}$ を満たす整数 $r$ $(0 \leq r < 998244353)$ が
一意に定まることが保証されるので、この $r$ を求めてください。

制約

• $1 \leq N \leq 1500$

• $2 \leq M \leq 10^{9}$

• $-10^{9} \leq X_{i}, Y_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

• $1 \leq H_{i} \leq M - 1$ $(1 \leq i \leq N)$

• $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$X_{1}$ $Y_{1}$ $H_{1}$
$X_{2}$ $Y_{2}$ $H_{2}$
   $\vdots$
$X_{N}$ $Y_{N}$ $H_{N}$

• $1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる

• $(1 + i)$ $(1 \leq i \leq N)$ 行目には $X_{i}, Y_{i}, H_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行ずつ合計 $N$ 行に出力してください。

$i$ $(1 \leq i \leq N)$ 行目には、$i$ 番目の問いに対する答えを出力してください。

サンプル

1 5
0 0 3

8

3 7
0 -2 5
2 0 4
-1 0 5

499122201
4
499122177

5 984744545
-146570235 -7990790 301202754
143580064 67918028 684955441
-43425514 -103157442 445005707
93700695 139883361 763292656
-1577876 104468051 352308994

603011850
593654922
420568561
57524703
424785206