There are $n$ line segments whose endpoints have integer coordinates. The left x-coordinate of each segment is $0$ and the right x-coordinate is $m$. The slope of each segment is an integer.

For each x-coordinate $0,1,\dots,m$, find the maximum point in any line segment.

Input

The first line has two integers $n$ and $m$: the number of line segments and the maximum x-coordinate.

The next $n$ lines describe the line segments. Each line has two integers $y_1$ and $y_2$: there is a line segment between points $(0,y_1)$ and $(m,y_2)$.

Output

Print $m+1$ integers: the maximum points for $x=0,1,\dots,m$.

Constraints

• $1 \le n, m \le 10^5$
• $0 \le y_1,y_2 \le 10^9$

Example

Input:

4 5
1 6
7 2
5 5
10 0

Output:

10 8 6 5 5 6