005 - 断層 (Geologic Fault)

時間制限 2 秒 / メモリ制限 256 MB / 得点 100 / x 0 /


TLE
2sec
MLE
256MB
得点
100

問題

 遠い昔,IOI 文明という高度な文明が栄えていた.しかし,火山の噴火により,この高度な文明はついに滅んでしまった.IOI 文明は直線状の河川に沿って繁栄しており,IOI 文明が滅んだとき,その地表面は平らであった.IOI 文明の跡地は座標平面の x 軸と見なすことができる.y 軸は高さ方向を表す.すなわち,座標平面において,直線 y = 0 は地表を,領域 y > 0 は地上を,領域 y < 0 は地下を表す.また,IOI 文明が滅んだとき,a 年前 (a ≥ 0) の地層は,直線 y = -a の位置にあった.
 IOI 文明が滅んだ後,IOI 文明の跡地では Q 回の地殻変動が起きた.i 回目 (1 ≤ iQ) の地殻変動は,位置 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 ≤ iN を満たす各整数 i について,点 (i - 1, 0) と点 (i, 0) の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを求めることである.

課題

 IOI 文明の跡地に起きたの情報が与えられたとき,すべての整数 i (1 ≤ iN) に対し,点 (i - 1, 0) と点 (i, 0) の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを出力せよ.

入力

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

  • 1 行目には, 2 個の整数 N, Q が空白を区切りとして書かれている.これは,答えを求める地点の数が N,地殻変動の回数が Q であることを表す.
  • 続く Q 行のうちの i 行目 (1 ≤ iQ) には,3 個の整数 Xi, Di, Li が空白を区切りとして書かれている.これは,i 回目の地殻変動の位置が Xi,方向が Di,変動の量が Li であることを表す.

出力

 出力は N 行からなる.標準出力の i 行目 (1 ≤ iN) には,点 (i - 1, 0) と点 (i, 0) の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを表す整数を出力せよ.

制限

 すべての入力データは以下の条件を満たす.

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ Q ≤ 200 000.
  • -1 000 000 000 ≤ Xi ≤ 1 000 000 000 (1 ≤ iQ).
  • 1 ≤ Di ≤ 2 (1 ≤ iQ).
  • 1 ≤ Li ≤ 1 000 000 000 (1 ≤ iQ).

小課題

小課題 1 [18 点]

 以下の条件を満たす.

  • N ≤ 100.
  • Q ≤ 100.
  • -100 ≤ Xi ≤ 100 (1 ≤ iQ).
  • Li = 1 (1 ≤ iQ).

小課題 2 [16 点]

 以下の条件を満たす.

  • N ≤ 3 000.
  • Q ≤ 3 000.

小課題 3 [66 点]

 追加の制限はない.

入出力例

入力例 1

10 2
12 1 3
2 2 2

出力例 1

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

 この入力例は,小課題 1 の制約を満たす.

入力例 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