Có \(n\) đoạn thẳng có hai đầu mút mang tọa độ nguyên. Mỗi tọa độ x nằm trong khoảng từ \(0\) đến \(m\). Hệ số góc của mỗi đoạn là một số nguyên.

Với mỗi tọa độ x \(0,1,\dots,m\), hãy tìm giá trị lớn nhất tại điểm đó trong số các đoạn thẳng. Nếu không có đoạn thẳng nào tại một điểm nào đó, giá trị lớn nhất là \(-1\).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng đoạn thẳng và tọa độ x lớn nhất.

\(n\) dòng tiếp theo mô tả các đoạn thẳng. Mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\) và \(y_2\): có một đoạn thẳng nối hai điểm \((x_1,y_1)\) và \((x_2,y_2)\).

Output

In ra \(m+1\) số nguyên: các giá trị lớn nhất tại \(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

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

-1 2 8 6 6 7