问题
수직선 위에 N개의 가로등이 있다.
모든 가로등은 처음 (0초)에 켜져 있으며 i번째 가로등은 Xi 위치에서 [Li, Ri] 구간에 빛을 비춘다.
i번째 가로등은 Ai초에 처음으로 꺼지고 이후 T초마다 자동으로 다시 꺼진다.
즉 모든 음이 아닌 정수 k에 대해 Ai + Tk 초에 켜져 있다면 꺼지게 된다.
수직선의 0번 위치에는 홍윤이의 집이 있다.
홍윤이는 겁이 아주 많아서 빛이 꺼지는 걸 무서워 한다.
집에서 자고 있다가도 가로등이 꺼졌다는 걸 알게 되면 바로 달려가서 가로등을 켜고 돌아온다.
이때 겁먹은 홍윤이의 속도는 아주 빨라서 이동 속도와 가로등을 켜는 속도 모두 무시할 수 있을 정도이다.
다만 겁이 너무 많은 나머지 조금이라도 빛이 비추지 않는 지점이 있다면 지나가지 못한다.
따라서 홍윤이는 도달할 수 없는 가로등은 다시 켜지 못하고 다른 가로등이 길을 밝혀주면 그제서야 달려가서 가로등을 켤 수 있다.
시간이 아주 많이 지나면 어떤 가로등들은 불이 꺼져 버린 채 다시는 켜지지 못하게 된다.
또 어떤 가로등들은 홍윤이가 계속 불을 켜주어 영원히 켜질 수 있게 된다.
우리의 할 일은 각 가로등들이 어떻게 될 지를 상상하는 것이다.
输入
다음과 같은 형식으로 입력이 주어진다.
<제한 조건>
1 \le N \le 300,000 1 \le A_i \le T \le 1,000,000,000 0 \le L_i < R_i \le 1,000,000,000 0 < X_i \le 1,000,000,000
<서브태스크>
#1 (11점) :
N\le 100 #2 (12점) :
N\le 1,000 #3 (25점) : 모든
A_i 는 서로 다르다.#4 (52점) : 추가적인 제약 조건이 없다.
输出
N줄에 걸쳐 각 가로등의 최종 상태를 출력하라.
i번 가로등이 영원히 꺼지지 않는다면, 다시 말해 어떤 순간 t에 대해서도 t 이후의 가로등이 켜져 있는 순간 t'이 존재한다면 -1을 출력하라.
i번 가로등이 언젠가 꺼지고 이후 다시는 켜지지 않게 된다면 마지막으로 꺼지게 된 순간의 시간을 초 단위로 출력하라.
示例 #1
4 10
5 0 4 3
2 0 3 1
7 2 6 9
3 7 8 4
13
21
9
24
示例 #2
4 10
3 4 5 5
7 0 4 6
5 0 6 5
8 0 7 7
25
16
25
7
示例 #3
2 7
2 0 5 3
3 0 2 4
-1
-1
示例 #4
8 1000
3 0 4 17
6 0 7 9
8 5 9 14
11 1 12 7
15 2 16 9
17 13 18 5
19 10 20 9
21 14 22 13
1017
1009
1014
1007
9
1005
9
13
需要登录才能编写代码。