Problem Statement

There are $N$ street lights on a number line. The $i\ (1\leq i\leq N)$-th street light is located at coordinate $A_i$ and has light intensity $B_i$.
Each street light illuminates its own location with a brightness equal to its light intensity, but the intensity decreases by $1$ for every $1$ of distance away, and becomes $0$ at distances greater than or equal to the light intensity of that street light.
That is, the light intensity of street light $i$ at coordinate $x$ is $\max(B_i - |x-A_i|,0)$.
The brightness of coordinate $x$ is the maximum of the light intensities of all street lights at coordinate $x$.
Write a program that finds the brightness of coordinate $j\ (1\leq j\leq X)$.

Input

$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$
• All inputs are integers.

Output

Let $L_x$ be the brightness of coordinate $x$. Output the brightness of coordinate $j\ (1\leq j\leq X)$, separated by spaces.

$L_1\ L_2\dots L_X$

Sample

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