문제
먼 옛날, IOI 문명이라는 고도의 문명이 번성하였다. 그러나 화산 폭발로 인해 이 문명은 멸망하고 말았다. IOI 문명은 직선 형태의 강을 따라 번영하였으며, 멸망 당시 그 표면은 평평하였다. IOI 문명의 유적지는 좌표 평면의 x축으로 간주할 수 있다. y축은 높이 방향을 나타낸다. 즉, 좌표 평면에서 직선 y = 0은 지표를, y > 0은 지상, y < 0은 지하를 나타낸다. 또한, IOI 문명이 멸망했을 때, a년 전(a ≧ 0)의 지층은 직선 y = −a의 위치에 있었다.
IOI 문명이 멸망한 이후, 이 유적지에서는 Q번의 지각 변동이 일어났다. i번째 지각 변동(1 ≦ i ≦ Q)은 위치 Xi, 방향 Di, 변동량 Li로 나타낼 수 있다. Di는 1 또는 2이다. i번째 지각 변동은 다음 두 단계로 일어난다.
1. 지층이 다음과 같이 이동한다.
Di = 1일 경우, 단층이 점 (Xi, 0)을 지나는 기울기 1의 직선에 따라 형성되며, 이 직선보다 위쪽에 있는 지층이 직선을 따라 높이 Li만큼 이동한다. 즉, 이 직선보다 위쪽에 있는 점 (x, y)는 점 (x + Li, y + Li)로 이동한다.
Di = 2일 경우, 단층이 점 (Xi, 0)을 지나는 기울기 −1의 직선에 따라 형성되며, 이 직선보다 위쪽에 있는 지층이 직선을 따라 높이 Li만큼 이동한다. 즉, 이 직선보다 위쪽에 있는 점 (x, y)는 점 (x − Li, y + Li)로 이동한다.
2. 직후, y > 0의 영역에 있는 지층은 풍화로 인해 모두 사라진다.
시대가 흘러 현대에, 고고학자인 JOI 박사는 IOI 문명의 유적을 발굴하기로 하였다. JOI 박사는 어느 위치의 지표 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인지 알고 싶어 한다. 어떤 지각 변동이 일어났는지는 알고 있다. 당신의 임무는 JOI 박사를 대신하여 1 ≦ i ≦ N을 만족하는 각 정수 i에 대해, 점 (i − 1, 0)과 점 (i, 0) 사이의 지표 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인지 구하는 것이다.
입력
첫 번째 줄에는 두 개의 정수 N, Q가 공백으로 구분되어 주어진다. 이는 답을 구해야 하는 지점의 수가 N, 지각 변동의 횟수가 Q임을 나타낸다.
이어지는 Q개의 줄 중 i번째 줄(1 ≦ i ≦ Q)에는 세 개의 정수 Xi, Di, Li가 공백으로 구분되어 주어진다. 이는 i번째 지각 변동의 위치가 Xi, 방향이 Di, 변동량이 Li임을 나타낸다.
1 ≦ N ≦ 200,000
1 ≦ Q ≦ 200,000
−1,000,000,000 ≦ Xi ≦ 1,000,000,000 (1 ≦ i ≦ Q)
1 ≦ Di ≦ 2 (1 ≦ i ≦ Q)
1 ≦ Li ≦ 1,000,000,000 (1 ≦ i ≦ Q)
출력
i번째 줄(1 ≦ i ≦ N)에는 점 (i − 1, 0)과 점 (i, 0) 사이의 지표 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인지 나타내는 정수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 18점 |
|
| #2 | 16점 |
|
| #3 | 66점 |
|
예제1
102
1213
222
3
3
5
5
5
5
5
5
2
2
지각 변동 과정이 다음 그림과 같다.
예제2
106
1411
1711
-621
321
411
021
5
5
4
5
5
5
5
5
4
4
서브태스크 1의 제한 조건을 만족한다.
예제3
1510
2817
-2421
111
811
621
2013
1222
-1013
721
512
15
14
14
14
14
12
12
12
12
12
12
12
15
15
12