很久以前，IOI 文明是一个高度发达的文明。然而，由于火山喷发，这个高度发达的文明最终灭亡了。IOI 文明沿着一条直线河流繁荣发展，在 IOI 文明灭亡时，其地表面是平坦的。IOI 文明的遗址可以看作坐标平面上的 $x$ 轴。$y$ 轴表示高度方向。也就是说，在坐标平面上，直线 $y = 0$ 表示地表，区域 $y > 0$ 表示地上，区域 $y < 0$ 表示地下。此外，在 IOI 文明灭亡时，$a$ 年前 ($a \ge 0$) 的地层位于直线 $y = -a$ 的位置。

在 IOI 文明灭亡后，IOI 文明的遗址发生了 $Q$ 次地壳变动。第 $i$ 次 ($1 \le i \le 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 \le i \le N$ 的每个整数 $i$，求出点 $(i-1, 0)$ 和点 $(i, 0)$ 之间的地表地层是 IOI 文明灭亡前多少年的地层。

输入格式

从标准输入读取以下内容：

• 第 1 行包含两个整数 $N, Q$，以空格分隔。这表示需要求出答案的地点数量为 $N$，地壳变动的次数为 $Q$。
• 接下来的 $Q$ 行中，第 $i$ 行 ($1 \le i \le Q$) 包含三个整数 $X_i, D_i, L_i$，以空格分隔。这表示第 $i$ 次地壳变动的位置为 $X_i$，方向为 $D_i$，变动量为 $L_i$。

输出格式

输出由 $N$ 行组成。标准输出的第 $i$ 行 ($1 \le i \le N$) 应输出一个整数，表示点 $(i - 1, 0)$ 和点 $(i, 0)$ 之间的地表地层是 IOI 文明灭亡前多少年的地层。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le Q$)
• $1 \le D_i \le 2$ ($1 \le i \le Q$)
• $1 \le L_i \le 1\,000\,000\,000$ ($1 \le i \le Q$)

子任务

子任务 1 [18 点]

满足以下条件： $N \le 100$ $Q \le 100$ $-100 \le X_i \le 100$ ($1 \le i \le Q$) $L_i = 1$ ($1 \le i \le Q$)

子任务 2 [16 点]

满足以下条件： $N \le 3\,000$ $Q \le 3\,000$

子任务 3 [66 点]

没有额外限制。

样例

输入格式 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