配点: 100 点
在遥远的过去,一种名为IOI文明的高级文明蓬勃发展。然而,这个先进的文明最终因火山爆发而灭亡。 IOI文明沿着笔直的河流繁盛,当IOI文明消亡时,地表平坦。 IOI文明废墟在坐标平面上。 x 可以将其视为一个轴。y 轴表示高度方向。也就是说,在坐标平面中,直线 y = 0 代表地球表面,面积 y > 0 覆盖地面和区域 y < 0 代表地下。还有,当IOI文明灭亡时,a 年前 (a \geqq 0) 是一条直线。 它位于 y = -a 。
IOI文明毁灭后,在IOI文明遗址, Q 发生了地壳运动。i 回目 (1 \leqq i \leqq 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 \leqq i \leqq N 的整数 对于 i ,点 (i - 1, 0) 和点 (i, 0)目的是查出IOI文明在多少年前被毁灭。
課題
IOI 鉴于文明所在地发生的事情的信息,所有整数 i (1 \leqq i \leqq N),这一点 输出IOI文明灭绝前多少年,地球表面的地层 (i - 1, 0) 和点 (i, 0) 之间。
入力
从标准输入读取以下输入。 在
- 1 行中,2 整数 N, Q 以空格作为分隔符。这意味着寻求答案的点数是 N,地壳运动次数为 Q 。
- 继续 来自行 Q 行 i 行目 (1 \leqq i \leqq Q)有3 整数 X_i, D_i, L_i 以空格作为分隔符。这是i 第二次地壳形变的位置是 X_i,方向是 D_i,变化量为 L_i 。
出力
输出是 由 N 行组成。标准输出 i 行目 (1 \leqq i \leqq N)有一点 输出一个整数,表示 (i - 1, 0) 和点 (i, 0) 之间地球表面的地层距离IOI文明灭绝还有多少年。
制限
所有输入数据满足以下条件。
- 1 \leqq N \leqq 200\,000.
- 1 \leqq Q \leqq 200\,000.
- -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q).
- 1 \leqq D_i \leqq 2 (1 \leqq i \leqq Q).
- 1 \leqq L_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q).
小課題
小課題 1 [18 点]
满足以下条件。
- N \leqq 100.
- Q \leqq 100.
- -100 \leqq X_i \leqq 100 (1 \leqq i \leqq Q).
- L_i = 1 (1 \leqq i \leqq Q).
小課題 2 [16 点]
满足以下条件。
- N \leqq 3,000.
- Q \leqq 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
这个输入示例是 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