AT_joi2016ho_e 断層 (Geologic Fault)

很久以前，存在着一个高度发达的文明，被称为 IOI 文明。然而，由于火山喷发，这个高度发达的文明最终灭亡了。IOI 文明沿着一条直线状的河流繁荣发展，在 IOI 文明灭亡时，其地表是平坦的。IOI 文明的遗址可以视为坐标平面上的 $x$ 轴，$y$ 轴表示高度方向。也就是说，在坐标平面中，直线 $y=0$ 表示地表，区域 $y>0$ 表示地上，区域 $y0$ 的地层因风化全部消失。 时光流转至现代，考古学家 JOI 博士开始发掘 IOI 文明的遗迹。JOI 博士想知道每个位置的地表地层，是 IOI 文明灭亡前多少年的地层。已知所有地壳变动的情况。你的任务是，代替 JOI 博士，对于每个满足 $1\leq i\leq N$ 的整数 $i$，求出点 $(i-1,0)$ 与点 $(i,0)$ 之间的地表地层，是 IOI 文明灭亡前多少年的地层。

从标准输入读取如下内容。 - 第 $1$ 行包含两个整数 $N, Q$，用空格分隔。表示需要求解的地点数量为 $N$，地壳变动的次数为 $Q$。 - 接下来的 $Q$ 行中，第 $i$ 行（$1\leq i\leq Q$）包含三个整数 $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 文明灭亡前多少年的地层的整数。

## 任务 已知 IOI 文明遗址上发生的所有地壳变动，对于每个整数 $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 [18 分] 满足以下条件： - $N\leq 100$。 - $Q\leq 100$。 - $-100\leq X_i\leq 100$（$1\leq i\leq Q$）。 - $L_i=1$（$1\leq i\leq Q$）。 ### 子任务 2 [16 分] 满足以下条件： - $N\leq 3,000$。 - $Q\leq 3,000$。 ### 子任务 3 [66 分] 无额外限制。 ## 样例说明 1 该输入示例对应下图。  ## 样例说明 2 该输入示例满足子任务 $1$ 的限制。 由 ChatGPT 4.1 翻译