There are $n$ line segments whose endpoints have integer coordinates. Each x-coordinate is between $0$ and $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. If there is no segment at some point, the maximum is $-1$.

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 four integers $x_1$, $y_1$, $x_2$ and $y_2$: there is a line segment between points $(x_1,y_1)$ and $(x_2,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 x_1 < x_2 \le m$
• $0 \le y_1,y_2 \le 10^9$

Example

Input:

4 5
1 1 3 3
1 2 4 2
2 4 5 7
2 8 5 2

Output:

-1 2 8 6 6 7