Geologic Fault

Time Limit : 2 sec, Memory Limit : 262144 KB

断層(Geologic Fault)

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

IOI 文明が滅んだ後,IOI 文明の跡地では $Q$ 回の地殻変動が起きた.$i$ 回目$(1 \leq i \leq 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 \leq i \leq N$ を満たす各整数 $i$ について,点$(i-1, 0)$ と点$(i, 0)$の間の地表の地層がIOI 文明が滅ぶ何年前の地層であるかを求めることである.

課題

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

入力

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

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

出力

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

制限

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

  • $1 \leq N \leq 200 000$
  • $1 \leq Q \leq 200 000$
  • $ -1 000 000 000 \leq X_i \leq 1 000 000 000$ $(1 \leq i \leq Q)$
  • $1 \leq D_i \leq 2$ $(1 \leq i \leq Q)$
  • $1 \leq L_i \leq 1 000 000 000$ $(1 \leq i \leq Q)$

入出力例

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

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

Source: 15th Japanese Olympiad in Informatics , 2016-2-14
http://www.ioi-jp.org/