Problem Description

Long ago, there was a highly advanced civilization known as the IOI Civilization. However, this advanced civilization eventually perished due to volcanic eruptions. The IOI Civilization flourished along a linear river, and at the time of its demise, the surface of the land was flat. The site of the IOI Civilization can be considered as the $x$ axis on a coordinate plane. The $y$ axis represents the height direction. That is, on the coordinate plane, the line $y = 0$ represents the surface, the region $y > 0$ represents the above-ground, and the region $y < 0$ represents the underground. Also, at the time of the IOI Civilization's demise, the strata from $a$ years ago ($a \geq 0$) were located on the line $y = -a$.

After the IOI Civilization perished, there were $Q$ instances of crustal movement at the site of the IOI Civilization. The $i$-th ($1 \leq i \leq Q$) crustal movement is represented by the position $X_i$, direction $D_i$, and the amount of movement $L_i$. $D_i$ is either $1$ or $2$. The $i$-th crustal movement occurs as follows:

• The movement of the strata occurs as follows:
• When $D_i = 1$, a fault is created along the line passing through the point $(X_i, 0)$ with a slope of $1$, and the strata in the region above this line move along the line by a height of $L_i$. That is, the point $(x, y)$ above this line moves to the point $(x + L_i, y + L_i)$.
• When $D_i = 2$, a fault is created along the line passing through the point $(X_i, 0)$ with a slope of $-1$, and the strata in the region above this line move along the line by a height of $L_i$. That is, the point $(x, y)$ above this line moves to the point $(x - L_i, y + L_i)$.
• Immediately afterward, all strata in the region $y > 0$ are eroded away.

Time has passed, and in modern times, archaeologist Dr. JOI has decided to excavate the ruins of the IOI Civilization. Dr. JOI wants to know how many years ago the surface strata at each location were from the time the IOI Civilization perished. You are tasked with determining, for each integer $i$ ($1 \leq i \leq N$), how many years ago the surface strata between the points $(i - 1, 0)$ and $(i, 0)$ were from the time the IOI Civilization perished.

Input Format

Read the following input from standard input:

• The first line contains two integers $N$ and $Q$ separated by a space. This indicates that there are $N$ locations to find the answer for and $Q$ instances of crustal movement.
• The next $Q$ lines each contain three integers $X_i$, $D_i$, and $L_i$ separated by spaces. This represents the position $X_i$, direction $D_i$, and amount of movement $L_i$ for the $i$-th crustal movement.

Output Format

The output consists of $N$ lines. The $i$-th line ($1 \leq i \leq N$) should contain an integer representing how many years ago the surface strata between the points $(i - 1, 0)$ and $(i, 0)$ were from the time the IOI Civilization perished.

Sample Input and Output

Sample Input #1

10 2
12 1 3
2 2 2

Sample Output #1

3
3
5
5
5
5
5
5
2
2

Sample Input #2

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

Sample Output #2

5
5
4
5
5
5
5
5
4
4

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

Sample Output #3

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

Notes/Hints

Task

Given the information about the crustal movements that occurred at the site of the IOI Civilization, for all integers $i$ ($1 \leq i \leq N$), output how many years ago the surface strata between the points $(i - 1, 0)$ and $(i, 0)$ were from the time the IOI Civilization perished.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [18 points]

Satisfies the following conditions:

• $N \leq 100$.
• $Q \leq 100$.
• $-100 \leq X_i \leq 100$ ($1 \leq i \leq Q$).
• $L_i = 1$ ($1 \leq i \leq Q$).

Subtask 2 [16 points]

Satisfies the following conditions:

• $N \leq 3,000$.
• $Q \leq 3,000$.

Subtask 3 [66 points]

No additional constraints.

Sample Explanation 1

This input example corresponds to the following diagram:

Sample Explanation 2

This input example satisfies the constraints of Subtask 1.

见题面 Input 部分

见题面 Output 部分