(本题翻译转自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