시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 4 4 4 100.000%

문제

먼 옛날, IOI 문명이라는 고도의 문명이 번성했다. 그러나 화산 분화로 인해이 고도의 문명은 결국 망하고 말았다. IOI 문명은 직선 모양의 하천을 따라 번영하였고, IOI 문명이 멸망했을 때, 그 지표면은 평평했다. IOI 문명의 유적지는 좌표 평면의 x축으로 간주할 수있다. y축은 높이 방향을 나타낸다. 즉, 좌표 평면에서, 직선 y = 0 은 지표를, 영역 y > 0 은 지상을, 영역 y < 0 은 지하를 나타낸다. 또한 IOI 문명이 멸망했을 때, a 년전 (a ≧ 0) 지층은 직선 y = -a 의 위치에 있었다.

IOI 문명이 멸망한 후 IOI 문명의 유적지에서는 Q 번의 지각 변동이 일어났다. i 번째 (1 ≦ i ≦ Q)의 지각 변동은 위치 Xi, 방향 Di, 변동의 양 Li로 표현된다. Di는 1 또는 2이다. i번째의 지각 변동은 다음과 같이 일어난다.

  • 지층의 이동이 다음과 같이 일어난다.
    • Di = 1 일 때, 단층이 점 (Xi, 0)을 지나는 기울기 1의 직선을 따라 만들어져, 이 직선보다 위쪽의 영역에 있는 지층이, 직선을 따라 높이 Li만큼 이동한다. 즉, 이 직선보다 위쪽에 있는 점 (x, y)는 점 (x + Li, y + Li)로 이동한다.
    • Di = 2 일 때, 단층이 점 (Xi, 0)을 지나는 기울기 -1의 직선을 따라 만들어져, 이 직선보다 위쪽의 영역에 있는 지층이, 직선을 따라 높이 Li만큼 이동한다. 즉, 이 직선보다 위쪽에 있는 점 (x, y)는 점 (x - Li, y + Li)로 이동한다.
  • 그 직후, 영역 y > 0 의 지층이 풍화에 의해 모두 사라진다.

시간이 흘러 현대에, 고고학자 JOI 박사는 IOI 문명의 유적을 발굴하기로했다. JOI 박사는 어느 위치의 표면의 지층이 IOI 문명이 멸망하기 몇 년전의 지층인지 알고 싶다. 그동안 어떤 지각 변동이 일어났는지는 알고 있다. 당신의 작업은 JOI 박사를 대신하여 1 ≦ i ≦ N 을 만족하는 각각의 정수 i에 대해, 점 (i-1, 0)과 점 (i, 0) 사이의 표면의 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인가를 알아내는 것이다.

IOI 문명의 유적지에 일어난 지각변동의 정보가 주어졌을 때, 모든 정수 i (1 ≦ i ≦ N)에 대해 점 (i - 1, 0)과 점 (i, 0) 사이의 표면의 지층 이 IOI 문명이 멸망하기 몇 년 전의 지층인가를 출력하라.

입력

표준입력으로 아래의 정보를 읽어들여라.

첫째 줄에는 두 개의 정수 N, Q가 공백을 사이에 두고 주어진다. 이는 답을 구해야 하는 지층의 수가 N, 지각변동의 수가 Q라는 것을 나타낸다.

이어 Q개의 줄 중 i번째 줄 (1 ≦ i ≦ Q) 에는, 세 개의 정수 Xi, Di, Li가 공백을 사이에 두고 주어진다. 이는 지각변동의 위치가 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).

 

출력

출력은 N개의 줄로 되어있다.

표준출력의 i번째 줄 (1 ≦ i ≦ N) 에는, 점 (i − 1, 0) 과 점 (i, 0) 의 사이의 지표의 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인가를 나타내는 정수를 출력한다.

예제 입력

10 2
12 1 3
2 2 2

예제 출력

3
3
5
5
5
5
5
5
2
2

예제 입력 2

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

예제 출력 2

5
5
4
5
5
5
5
5
4
4

예제 입력 3

15 10
28 1 7
-24 2 1
1 1 1
8 1 1
6 2 1
20 1 3
12 2 2
-10 1 3
7 2 1
5 1 2

예제 출력 3

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12

힌트

2016-ho-20.jpg

출처

Olympiad > 일본정보올림피아드 > JOI 2016 5번