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

IOI 文明が滅んだ後，IOI 文明の跡地では Q 回の地殻変動が起きた．i 回目 (1 \leqq i \leqq Q) の地殻変動は，位置 X_i，方向 D_i，変動の量 L_i で表される．D_i は 1 または 2 である．i 回目の地殻変動は以下のように起きる．

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

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

課題

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

制限

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

• 1 \leqq N \leqq 200\,000．
• 1 \leqq Q \leqq 200\,000．
• -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q)．
• 1 \leqq D_i \leqq 2 (1 \leqq i \leqq Q)．
• 1 \leqq L_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q)．

小課題

小課題 1 [18 点]

以下の条件を満たす．

• N \leqq 100．
• Q \leqq 100．
• -100 \leqq X_i \leqq 100 (1 \leqq i \leqq Q)．
• L_i = 1 (1 \leqq i \leqq Q)．

小課題 2 [16 点]

以下の条件を満たす．

• N \leqq 3,000．
• Q \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

この入力例は，以下の図に対応する．

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