AT_joi2016ho_e 断層 (Geologic Fault)

[problemUrl]: https://atcoder.jp/contests/joi2016ho/tasks/joi2016ho_e 遠い昔，IOI 文明という高度な文明が栄えていた．しかし，火山の噴火により，この高度な文明はついに滅んでしまった．IOI 文明は直線状の河川に沿って繁栄しており，IOI 文明が滅んだとき，その地表面は平らであった．IOI 文明の跡地は座標平面の $ x $ 軸と見なすことができる．$ y $ 軸は高さ方向を表す．すなわち，座標平面において，直線 $ y\ =\ 0 $ は地表を，領域 $ y\ >\ 0 $ は地上を，領域 $ y\ \ 0 $ の地層が風化によってすべて消える． 時は変わり現代，考古学者の JOI 博士は IOI 文明の遺跡を発掘することにした．JOI 博士はどの位置の地表の地層が，IOI 文明が滅ぶ何年前の地層であるかを知りたい．どのような地殻変動が起きたかは分かっている．あなたの仕事は，JOI 博士にかわって，$ 1\ \leqq\ i\ \leqq\ N $ を満たす各整数 $ i $ について，点 $ (i\ -\ 1,\ 0) $ と点 $ (i,\ 0) $の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを求めることである．

標準入力から以下の入力を読み込め． - $ 1 $ 行目には，$ 2 $ 個の整数 $ N,\ Q $ が空白を区切りとして書かれている．これは，答えを求める地点の数が $ N $，地殻変動の回数が $ Q $ であることを表す． - 続く $ Q $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ Q $) には，$ 3 $ 個の整数 $ X_i,\ D_i,\ L_i $ が空白を区切りとして書かれている．これは，$ i $ 回目の地殻変動の位置が $ X_i $，方向が $ D_i $，変動の量が $ L_i $ であることを表す．

出力は $ N $ 行からなる．標準出力の $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N $) には，点 $ (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 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 この入力例は，以下の図に対応する． !\[2016-ho-t5-fig01.png\](https://img.atcoder.jp/joi2016ho/2016-ho-t5-fig01.png) - - - - - - ### Sample Explanation 2 この入力例は，小課題 $ 1 $ の制約を満たす． - - - - - -