問題文

$N × N$ マスの $2$ 次元グリッドがあります。
上から $i$ 行目、左から $j$ 列目のマス $(i, j)$ には、それぞれ高度が設定されており、全てのマスにおいて高度は $0$ です。
やきとりくんは、この $2$ 次元グリッドに $M$ 個の爆弾を落とすことにしました。
$i \: (1 ≦ i ≦ M)$ 個目の爆弾は、威力が $P_i$ で、マス $(R_i, C_i)$ に落下します。
また、威力が $P_i$ の爆弾は、落下したマスからのマンハッタン距離が $P_i$ 以下のマスの高度を $1$ 低下させます。

爆弾を $M$ 個落とした後の高度が $0, -1, -2, … ,-M$ であるマスの個数をそれぞれ出力してください。

なお、マス $(x_1, y_1)$ と マス $(x_2, y_2)$ のマンハッタン距離は、$|x_1 - y_1| + |x_2 - y_2|$ で定義されます。

制約

• $1 \leq N \leq 1000$
• $1 \leq M \leq 10^5$
• $1 \leq P_i \leq 10^5 \: (1 \leq i \leq M)$
• $1 \leq R_i, C_i \leq N \: (1 \leq i \leq M)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
P_1 R_1 C_1
P_2 R_2 C_2
……
P_M R_M C_M

出力

高度が $0, -1, -2, … , -M$ であるマスの個数をそれぞれ空白区切りで出力せよ。

入出力例

5 2
1 3 2
1 3 4

16 8 1

爆弾が落ちた後の $2$ 次元グリッドの高度は以下のようになっています。

 0  0  0  0  0
 0 -1  0 -1  0
-1 -1 -2 -1 -1
 0 -1  0 -1  0
 0  0  0  0  0

1 3
100 1 1
100 1 1
100 1 1

0 0 0 1

同じマスに爆弾が何回も落下することがあることや、$2$ 次元グリッドの外のことについては考えないことに注意してください。

20 10
6 4 12
1 10 4
8 20 3
6 17 3
9 5 16
8 4 6
5 15 11
8 4 6
3 16 9
7 18 6

63 102 127 66 40 2 0 0 0 0 0