Problem Description

The translator’s ability is limited; I sincerely ask everyone to provide a better translation.

This problem is translated from JOI 2016 Final T5 “断層”.

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

The IOI civilization developed along a straight river. For convenience, the ruins of the IOI civilization can be regarded as the $x$ axis of the Cartesian coordinate plane, and the $y$ axis represents altitude. The ground surface of the IOI civilization is flat; that is, the line $y=0$ represents the ground, $y>0$ is above the ground, and $y<0$ is underground. In addition, due to sediment deposition, the ground of the IOI civilization kept rising slowly. At $a$ years before the fall of the IOI civilization $(a\geqslant 0)$, the line $y=-a$ was the ground surface.

After the IOI civilization fell, the strata beneath it moved $Q$ times. The $i$-th movement $(1\leqslant i\leqslant Q)$ is described by position $X_i$, direction $D_i$, and amount $L_i$. $D_i$ is $1$ or $2$. Specifically,

• $D_i=1$: The fault is considered to be a line passing through $(X_i, 0)$ with slope $1$. The strata above the fault move diagonally upward: the $x$ coordinate increases by $L_i$, and the $y$ coordinate increases by $L_i$. That is, every point $(x,y)$ above the line moves to $(x+L_i, y+L_i)$.
• $D_i=2$: The fault is considered to be a line passing through $(X_i, 0)$ with slope $-1$. The strata above the fault move diagonally upward: the $x$ coordinate decreases by $L_i$, and the $y$ coordinate increases by $L_i$. That is, every point $(x,y)$ above the line moves to $(x-L_i, y+L_i)$.

After each crustal movement, all strata with $y>0$ disappear due to weathering.

You are asked: for each $i$ $(1\leqslant i\leqslant N)$, determine which year before the fall of the IOI civilization the stratum between point $(i-1,0)$ and point $(i,0)$ comes from.

On the $y$ axis, every fault passes through an integer point, and there is no fault between two adjacent integer points on the $y$ axis. This should be clear, right……

Input Format

The first line contains two integers $N, Q$, separated by spaces.
In the next $Q$ lines, the $i$-th line $(1\leqslant i\leqslant Q)$ contains three integers $X_i, D_i, L_i$, separated by spaces.
The meanings of all input values are given in the statement.

Output Format

Output $N$ lines in total.
The $i$-th line $(1\leqslant i\leqslant N)$ contains one integer, indicating which year before the fall of the IOI civilization the stratum between point $(i-1,0)$ and point $(i,0)$ comes from.

10 2
12 1 3
2 2 2

3
3
5
5
5
5
5
5
2
2

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

5
5
4
5
5
5
5
5
4
4

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

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

Hint

Sample Explanation 1

Constraints and Notes

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

Translated by ChatGPT 5