#T2228. 线段追踪 I(Line Segments Trace I)

线段追踪 I(Line Segments Trace I)

链接: https://cses.fi/problemset/task/3427

板块: Geometry

时限: 1.00 s | 内存: 512 MB

题目描述

有 nn 条线段,其端点坐标均为整数。每条线段的左端点横坐标为 00,右端点横坐标为 mm。每条线段的斜率均为整数。

对每个横坐标 0,1,…,m0,1,\dots,m,求出所有线段在该处的最大纵坐标。

输入

第一行包含两个整数 nn 和 mm:线段的数量以及最大的横坐标。

接下来 nn 行描述这些线段。每行包含两个整数 y1y_1 和 y2y_2:存在一条连接点 (0,y1)(0,y_1) 和 (m,y2)(m,y_2) 的线段。

输出

输出 m+1m+1 个整数:横坐标 x=0,1,…,mx=0,1,\dots,m 处的最大纵坐标。

数据范围

1≤n,m≤1051 \le n, m \le 10^5 0≤y1,y2≤1090 \le y_1,y_2 \le 10^9

样例输入

4 5
1 6
7 2
5 5
10 0

样例输出

10 8 6 5 5 6