0355 - 断層 (Geologic Fault)
問題
遠い昔，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