断層 (Geologic Fault)
题意翻译
(本题翻译转自[P5103](https://www.luogu.org/problemnew/show/P5103))
很久很久以前，一个叫做 IOI 的先进文明蓬勃发展。时过境迁，现代考古学家 JOI 博士决定挖掘 IOI 文明遗址。
IOI 文明沿着笔直的河流发展。方便起见，IOI 文明遗址可以看作平面直角坐标系的 $x$ 轴，而 $y$ 轴表示海拔。IOI 文明地面平坦，也就是说，直线 $y=0$ 代表地面，而 $y>0$ 代表地面上空，$y<0$ 代表地下。另外，由于流水堆积，IOI 文明的地面一直在缓慢升高。IOI 文明灭亡前 $a$ 年 $(a\geqslant 0)$ 时，直线 $y=-a$ 才是地平面。
IOI 文明灭亡后，它脚下的地层发生了 $Q$ 次运动。第 ii 次运动 $(1\leqslant i\leqslant Q)$ 可用位置 $X_i$，方向 $D_i$和变化量 $L_i$描述。$D_i = 1
$ 或 $2$。具体来说，
- $D_i=1$：断层视为一条过 $(X_i, 0)$，斜率为 $1$ 的直线。断层上方的地层斜向上移动，横坐标增加 $L_i$，纵坐标增加 $L_i$ 。也就是说，直线上方的所有点 $(x,y)$ 移动到 $(x+L_i, y+L_i)$。
- $D_i=2$：断层视为一条过 $(X_i, 0)$，斜率为 $-1$ 的直线。断层上方的地层斜向上移动，横坐标减少 $L_i$，纵坐标增加 $L_i$ 。也就是说，直线上方的所有点 $(x,y)$ 移动到 $(x-L_i, y+L_i)$。
每次地壳运动后，$y>0$ 的地层都会因风化作用而消失。
试求：对于每一个 $i(1\leqslant i\leqslant N)$，点 $(i-1,0)$ 和 点$(i,0)$ 之间的地层是在 IOI 文明灭亡前哪一年的地层。
> 在 $y$ 轴上，断层都是经过整点的，$y$ 轴上的相邻整点间没有断层。这样讲能明白吧……
第一行有两个整数 $N,Q$，用空格分隔。
在接下来的 $Q$ 行中，第 $i$ 行 $(1\leqslant i\leqslant N)$ 有三个整数 $X_i, D_i, L_i$，用空格分隔。
输入的所有数的含义见题目描述。
输出格式：
输出共 $N$ 行，第 $i$ 行 $(1\leqslant i\leqslant N)$ 有一个整数，表示点 $(i-1,0)$ 和 点$(i,0)$之间的地层是在 IOI 文明灭亡前哪一年的地层。
输入样例#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
```
说明
样例解释 1
数据范围与提示
对于所有数据，$1\leqslant N, Q\leqslant 2\times 10^5$, $-10^9\leqslant X_i\leqslant 10^9,$$D_i=1$ 或 $2$, $1\leqslant L_i\leqslant 10^9(1\leqslant i\leqslant Q)$。
Subtask # $N,Q$ 其他限制 分值
1 $N,Q\leqslant 100$ $-100\leqslant X_i\leqslant 100$, $L_i=1(1\leqslant i\leqslant Q)$ 18
2 $N,Q\leqslant 3000$ 无 16
3 $N,Q\leqslant 2\times10^5$ 无 66
题目描述
[problemUrl]: https://atcoder.jp/contests/joi2016ho/tasks/joi2016ho_e
遠い昔，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 文明が滅ぶ何年前の地層であるかを求めることである．
输入输出格式
输入格式
標準入力から以下の入力を読み込め．
- $ 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 文明が滅ぶ何年前の地層であるかを表す整数を出力せよ．
- - - - - -
输入输出样例
输入样例 #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说明
### 課題
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 $ の制約を満たす． - - - - - -