問題文

数直線上に $N$ 個の街灯があります。$i\ (1\leq i\leq N)$ 個目の街灯は座標 $A_i$ にあり、光の強さは $B_i$ です。
どの街灯も、その街灯と同じ地点を街灯の光の強さと同じ眩しさで照らしていますが、距離が $1$ 離れるごとに光の強さは $1$ 小さくなり、距離がその街灯の光の強さ以上離れると $0$ になります。
すなわち、街灯 $i$ の座標 $x$ での光の強さは $\max(B_i - |x-A_i|,0)$ です。
座標 $x$ の眩しさは、座標 $x$ における、全ての街灯の光の強さの最大値です。
座標 $j\ (1\leq j\leq X)$ の眩しさを求めるプログラムを作成してください。

入力

$N\ X$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

• $1\leq N\leq 1000$
• $1\leq X\leq 1000$
• $1\leq A_i\leq X$
• $1\leq B_i\leq 1000$
• 入力は全て整数

出力

座標 $x$ の眩しさを $L_x$ とします。座標 $j\ (1\leq j\leq X)$ の眩しさを空白区切りで出力してください。

$L_1\ L_2\dots L_X$

サンプル

2 5
1 2
4 3

2 1 2 3 2

5 6
5 3
2 1
3 4
5 3
3 6

4 5 6 5 4 3

10 20
1 1
5 18
3 12
8 5
6 10
8 7
19 6
20 11
6 16
19 16

14 15 16 17 18 17 16 15 14 13 12 11 10 11 12 13 14 15 16 15