题目描述

译者水平有限，跪求各位大佬提供更好的译文

本题译自 JOI 2016 Final T5「断層」

很久很久以前，一个叫做 IOI 的先进文明蓬勃发展。时过境迁，现代考古学家 JOI 博士决定挖掘 IOI 文明遗址。

IOI 文明沿着笔直的河流发展。方便起见，IOI 文明遗址可以看作平面直角坐标系的 $x$ 轴，而 $y$ 轴表示海拔。IOI 文明地面平坦，也就是说，直线 $y=0$ 代表地面，而 $y>0$ 代表地面上空，$y<0$ 代表地下。另外，由于流水堆积，IOI 文明的地面一直在缓慢升高。IOI 文明灭亡前 $a$ 年 $(a\geqslant 0)$ 时，直线 $y=-a$ 才是地平面。
IOI 文明灭亡后，它脚下的地层发生了 $Q$ 次运动。第 $i$ 次运动 $(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

input

10 2
12 1 3
2 2 2

output

3
3
5
5
5
5
5
5
2
2

样例 2

input

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

output

5
5
4
5
5
5
5
5
4
4

样例 3

input

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

output

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12

数据范围与提示

对于所有数据，$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)$。