Problem Description

This translation is provided by a translator with limited skills. Contributions for a better translation are welcome.

This problem is a translation of "Fault Line" from the JOI 2016 Final.

A long, long time ago, an advanced civilization called IOI flourished. As time passed, modern archaeologist Dr. JOI decided to excavate the ruins of the IOI civilization.

The IOI civilization developed along a straight river. For convenience, the IOI civilization ruins can be considered as the $x$-axis in a Cartesian coordinate system, with the $y$-axis representing altitude. The ground of the IOI civilization was flat, meaning the line $y=0$ represents the ground, $y>0$ represents the air above the ground, and $y<0$ represents underground. Additionally, due to sedimentation, the ground of the IOI civilization was gradually rising. $a$ years before the fall of the IOI civilization ($a \geq 0$), the line $y=-a$ was the ground level.

After the fall of the IOI civilization, the strata beneath it underwent $Q$ movements. The $i$-th movement ($1 \leq i \leq Q$) is described by the position $X_i$, direction $D_i$, and change $L_i$. $D_i$ can be 1 or 2. Specifically,

• $D_i=1$: The fault line is considered as a line passing through $(X_i, 0)$ with a slope of 1. The strata above the fault line move diagonally upwards, increasing the x-coordinate by $L_i$ and the y-coordinate by $L_i$. That is, all points $(x, y)$ above the line move to $(x+L_i, y+L_i)$.
• $D_i=2$: The fault line is considered as a line passing through $(X_i, 0)$ with a slope of -1. The strata above the fault line move diagonally upwards, decreasing the x-coordinate by $L_i$ and increasing the y-coordinate by $L_i$. That is, all points $(x, y)$ above the line move to $(x-L_i, y+L_i)$.

After each tectonic movement, the strata with $y>0$ will disappear due to weathering.

Determine: For each $i (1 \leq i \leq N)$, in which year before the fall of the IOI civilization was the stratum between points $(i-1, 0)$ and $(i, 0)$ formed.

On the $y$-axis, fault lines always pass through integer points, and there are no fault lines between adjacent integer points on the $y$-axis. Hope this clarifies...

Input Format

The first line contains two integers $N$ and $Q$, separated by a space.
The next $Q$ lines, the $i$-th line ($1 \leq i \leq N$) contains three integers $X_i, D_i, L_i$, separated by spaces.
The meanings of all input numbers are as described in the problem statement.

Output Format

Output consists of $N$ lines. The $i$-th line ($1 \leq i \leq N$) contains an integer representing the year before the fall of the IOI civilization when the stratum between points $(i-1, 0)$ and $(i, 0)$ was formed.

Sample Input and Output

Input Sample #1

10 2
12 1 3
2 2 2

Output Sample #1

3
3
5
5
5
5
5
5
2
2

Input Sample #2

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

Output Sample #2

5
5
4
5
5
5
5
5
4
4

Input Sample #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

Output Sample #3

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

Notes/Hints

Sample Explanation 1

Data Range and Hints

For all data, $1 \leq N, Q \leq 2 \times 10^5, -10^9 \leq X_i \leq 10^9, D_i=1$ or $2, 1 \leq L_i \leq 10^9 (1 \leq i \leq Q)$.

见题面 Input 部分

见题面 Output 部分