#P18718. Good Night

    ID: 18054 传统题 10000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-离散化区间合并差分标记区间修改懒标记线段树线段树上二分事件驱动模拟优先队列调度事件增量维护

Good Night

Good Night

一条笔直的道路上有 nn 盏路灯。道路用数轴表示,第 ii 盏路灯位于坐标 xix_i,照亮道路上的闭区间 [ℓi,ri][\ell_i,r_i]。初始时刻 00,所有路灯均亮着。此后,路灯会按固定周期自动熄灭,有时也会被重新打开。

第 ii 盏灯会在 ai,ai+t,ai+2t,ai+3t,…a_i,a_i+t,a_i+2t,a_i+3t,\ldots 时刻自动关闭。所有 aia_i 和共同周期 tt 都已知。

胆小的 Azber 住在原点 x=0x=0。他不敢经过任何没有路灯照亮的点,只有他居住的原点例外。如果他发现某盏熄灭的路灯可以从原点到达,就会飞快地跑过去将它打开,再直接回到原点。他的移动速度极快,所用时间可以忽略。

同一时刻自动关闭的路灯先同时熄灭;之后 Azber 可以不断打开从原点可达的熄灭路灯。某盏灯重新亮起后,可能使更多熄灭的灯可以到达。经过一段时间后,有些灯会永久熄灭。对每盏路灯,求它最后亮着的时刻;如果它不会永久熄灭,输出 −1-1。

输入格式

第一行两个整数 n,tn,t,1≤n≤3⋅1051\le n\le3\cdot10^5,1≤t≤1091\le t\le10^9。

接下来 nn 行,第 ii 行四个整数 xi,ℓi,ri,aix_i,\ell_i,r_i,a_i,分别为位置、照明区间两端点和首次自动关闭时刻,满足

$$0<x_i\le10^9,\quad0\le\ell_i<r_i\le10^9,\quad0<a_i\le t.$$

**原题不保证路灯的位置位于它自己的照明区间内。**位置、区间和首次关闭时刻也不要求互异。区间端点包含在照明范围内。

输出格式

输出 nn 行。第 ii 行若该灯永不永久熄灭,输出 −1-1;否则输出它最后亮着的时刻(即它未能再被打开的那次自动关闭时刻)。答案可能超过 32 位整数范围。

原样例

4 10
5 0 4 3
2 0 3 1
7 2 6 9
3 7 8 4
13
21
9
24
4 10
3 4 5 5
7 0 4 6
5 0 6 5
8 0 7 7
25
16
25
7
2 7
2 0 5 3
3 0 2 4
-1
-1