#joi2016hoe. [joi2016ho_e]断層 (Geologic Fault)

[joi2016ho_e]断層 (Geologic Fault)

遠い昔,IOI 文明という高度な文明が栄えていた.しかし,火山の噴火により,この高度な文明はついに滅んでしまった.IOI 文明は直線状の河川に沿って繁栄しており,IOI 文明が滅んだとき,その地表面は平らであった.IOI 文明の跡地は座標平面の xx 軸と見なすことができる.yy 軸は高さ方向を表す.すなわち,座標平面において,直線 y=0y = 0 は地表を,領域 y>0y > 0 は地上を,領域 y<0y < 0 は地下を表す.また,IOI 文明が滅んだとき,aa 年前 (ageqq0a \\geqq 0) の地層は,直線 y=ay = -a の位置にあった.

IOI 文明が滅んだ後,IOI 文明の跡地では QQ 回の地殻変動が起きた.ii 回目 (1leqqileqqQ1 \\leqq i \\leqq Q) の地殻変動は,位置 XiX_i,方向 DiD_i,変動の量 LiL_i で表される.DiD_i11 または 22 である.ii 回目の地殻変動は以下のように起きる.

  • 地層の移動が次のように起きる.
    • Di=1D_i = 1 のとき,断層が点 (Xi,0)(X_i, 0) を通る傾き 11 の直線に沿って造られ,この直線より上の領域にある地層が,直線に沿って高さ LiL_i だけ移動する.すなわち,この直線より上の点 (x,y)(x, y) は,点 (x+Li,y+Li)(x + L_i, y + L_i) に移動する.
    • Di=2D_i = 2 のとき,断層が点 (Xi,0)(X_i, 0) を通る傾き \-1\-1 の直線に沿って造られ,この直線より上の領域にある地層が,直線に沿って高さ LiL_i だけ移動する.すなわち,この直線より上の点 (x,y)(x, y) は,点 (xLi,y+Li)(x - L_i, y + L_i) に移動する.
  • そのすぐ後に,領域 y>0y > 0 の地層が風化によってすべて消える.

時は変わり現代,考古学者の JOI 博士は IOI 文明の遺跡を発掘することにした.JOI 博士はどの位置の地表の地層が,IOI 文明が滅ぶ何年前の地層であるかを知りたい.どのような地殻変動が起きたかは分かっている.あなたの仕事は,JOI 博士にかわって,1leqqileqqN1 \\leqq i \\leqq N を満たす各整数 ii について,点 (i1,0)(i - 1, 0) と点 (i,0)(i, 0)の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを求めることである.

課題

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


入力

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

  • 11 行目には,22 個の整数 N,QN, Q が空白を区切りとして書かれている.これは,答えを求める地点の数が NN,地殻変動の回数が QQ であることを表す.
  • 続く QQ 行のうちの ii 行目 (1leqqileqqQ1 \\leqq i \\leqq Q) には,33 個の整数 Xi,Di,LiX_i, D_i, L_i が空白を区切りとして書かれている.これは,ii 回目の地殻変動の位置が XiX_i,方向が DiD_i,変動の量が LiL_i であることを表す.

出力

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


制限

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

  • 1leqqNleqq200,0001 \\leqq N \\leqq 200\\,000
  • 1leqqQleqq200,0001 \\leqq Q \\leqq 200\\,000
  • $\-1\\,000\\,000\\,000 \\leqq X_i \\leqq 1\\,000\\,000\\,000$ (1leqqileqqQ1 \\leqq i \\leqq Q).
  • 1leqqDileqq21 \\leqq D_i \\leqq 2 (1leqqileqqQ1 \\leqq i \\leqq Q).
  • 1leqqLileqq1,000,000,0001 \\leqq L_i \\leqq 1\\,000\\,000\\,000 (1leqqileqqQ1 \\leqq i \\leqq Q).

小課題

小課題 1 [18 点]

以下の条件を満たす.

  • Nleqq100N \\leqq 100
  • Qleqq100Q \\leqq 100
  • \-100leqqXileqq100\-100 \\leqq X_i \\leqq 100 (1leqqileqqQ1 \\leqq i \\leqq Q).
  • Li=1L_i = 1 (1leqqileqqQ1 \\leqq i \\leqq Q).

小課題 2 [16 点]

以下の条件を満たす.

  • Nleqq3,000N \\leqq 3,000
  • Qleqq3,000Q \\leqq 3,000

小課題 3 [66 点]

追加の制限はない.


入力例 1

10 2
12 1 3
2 2 2

出力例 1

3
3
5
5
5
5
5
5
2
2

この入力例は,以下の図に対応する.

2016-ho-t5-fig01.png


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

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


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