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.

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)$ .

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

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