地表的地层年代确定问题

当IOI文明的遗址发生地壳变动时，我们需要确定每个位置的地表地层是在IOI文明灭亡前的多少年形成的。你的任务是代替JOI博士，对于每个整数$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文明灭亡前的多少年形成的。

输入

从标准输入中读入以下输入：

• 第一行包含两个整数$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文明灭亡前的多少年形成的，为一个整数。

约束条件

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

• $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

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

此示例满足子任务1的约束条件。

示例输入 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