Có \(n\) đoạn thẳng có hai đầu mút mang tọa độ nguyên. Tọa độ x bên trái của mỗi đoạn là \(0\) và tọa độ x bên phải là \(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.

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 hai số nguyên \(y_1\) và \(y_2\): có một đoạn thẳng nối hai điểm \((0,y_1)\) và \((m,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 y_1,y_2 \le 10^9\)

Example

4 5
1 6
7 2
5 5
10 0

10 8 6 5 5 6