#P18718. Good Night
Good Night
Good Night
一条笔直的道路上有 盏路灯。道路用数轴表示,第 盏路灯位于坐标 ,照亮道路上的闭区间 。初始时刻 ,所有路灯均亮着。此后,路灯会按固定周期自动熄灭,有时也会被重新打开。
第 盏灯会在 时刻自动关闭。所有 和共同周期 都已知。
胆小的 Azber 住在原点 。他不敢经过任何没有路灯照亮的点,只有他居住的原点例外。如果他发现某盏熄灭的路灯可以从原点到达,就会飞快地跑过去将它打开,再直接回到原点。他的移动速度极快,所用时间可以忽略。
同一时刻自动关闭的路灯先同时熄灭;之后 Azber 可以不断打开从原点可达的熄灭路灯。某盏灯重新亮起后,可能使更多熄灭的灯可以到达。经过一段时间后,有些灯会永久熄灭。对每盏路灯,求它最后亮着的时刻;如果它不会永久熄灭,输出 。
输入格式
第一行两个整数 ,,。
接下来 行,第 行四个整数 ,分别为位置、照明区间两端点和首次自动关闭时刻,满足
$$0<x_i\le10^9,\quad0\le\ell_i<r_i\le10^9,\quad0<a_i\le t.$$**原题不保证路灯的位置位于它自己的照明区间内。**位置、区间和首次关闭时刻也不要求互异。区间端点包含在照明范围内。
输出格式
输出 行。第 行若该灯永不永久熄灭,输出 ;否则输出它最后亮着的时刻(即它未能再被打开的那次自动关闭时刻)。答案可能超过 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