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