题目描述

有 $n$ 条线段，端点坐标均为整数。每个端点的横坐标都在 $0$ 到 $m$ 之间，且每条线段的斜率都是整数。

对于每个横坐标 $x=0,1,\ldots,m$，请找到所有线段在该横坐标处经过的点中纵坐标最大的点。如果没有任何线段经过该横坐标，答案为 $-1$。

输入格式

第一行包含两个整数 $n,m$，分别表示线段数量和最大横坐标。

接下来 $n$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一条连接 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的线段。

输出格式

输出 $m+1$ 个整数，依次表示 $x=0,1,\ldots,m$ 时的答案。

数据范围

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

样例

样例输入

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

样例输出

-1 2 8 6 6 7