시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 2 2 2 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 文明が滅ぶ何年前の地層であるかを出力せよ.

입력

標準入力から以下の入力を読み込め.

1 行目には, 2 個の整数 N, Q が空白を区切りとして書かれている.これは,答えを求める地点の数が N,地殻変動の回数が Q であることを表す.
続く Q 行のうちの i 行目 (1 ≦ i ≦ Q) には,3 個の整数 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).

출력

出力は 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

힌트