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 ≤ 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 であることを表す．

出力

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

制限

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

  • 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)．

小課題

小課題 1 [18 点]

　以下の条件を満たす．

  • N ≤ 100．
  • Q ≤ 100．
  • -100 ≤ Xi ≤ 100 (1 ≤ i ≤ Q)．
  • Li = 1 (1 ≤ i ≤ Q)．

小課題 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