Line Segments Trace I

题目描述

有 n 条线段，其端点坐标为整数。每条线段的左端点的 x 坐标为 0，右端点的 x 坐标为 m。每条线段的斜率为整数。 对于每个 x 坐标 0,1,$\dots$,m，求在所有线段中对应的最大点。

输入格式

第一行包含两个整数 n 和 m：线段的数量和最大的 x 坐标。 接下来的 n 行描述线段。每行有两个整数 y_1 和 y_2：存在一条线段连接点 (0,y_1) 和 (m,y_2)。

输出格式

输出 m+1 个整数：对应 x=0,1,$\dots$,m 的最大点。

4 5
1 6
7 2
5 5
10 0

10 8 6 5 5 6

提示

$1 \le n, m \le 10^5$ $0 \le y_1,y_2 \le 10^9$

标签: CSES3427|几何

来源

CSES3427|几何