P5103 [JOI 2016 Final] 断层 / Geologic Fault

**译者水平有限，跪求各位大佬提供更好的译文** **本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T5「[断層](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」** 很久很久以前，一个叫做 IOI 的先进文明蓬勃发展。时过境迁，现代考古学家 JOI 博士决定挖掘 IOI 文明遗址。 IOI 文明沿着笔直的河流发展。方便起见，IOI 文明遗址可以看作平面直角坐标系的 $x$ 轴，而 $y$ 轴表示海拔。IOI 文明地面平坦，也就是说，直线 $y=0$ 代表地面，而 $y>0$ 代表地面上空，$y0$ 的地层都会因风化作用而消失。 试求：对于每一个 $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  #### 数据范围与提示 对于所有数据，$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|