A long time ago, a highly advanced civilization called the IOI civilization flourished. However, due to a volcanic eruption, this advanced civilization finally perished. The IOI civilization flourished along a linear river, and when the IOI civilization perished, its ground surface was flat. The site of the IOI civilization can be regarded as the $x$-axis of a coordinate plane. The $y$-axis represents the height direction. That is, in the coordinate plane, the line $y = 0$ represents the ground surface, the region $y > 0$ represents above ground, and the region $y < 0$ represents underground. Also, when the IOI civilization perished, the stratum $a$ years ago ($a \ge 0$) was located at the line $y = -a$.

After the IOI civilization perished, $Q$ crustal movements occurred at the site of the IOI civilization. The $i$-th ($1 \le i \le Q$) crustal movement is represented by its position $X_i$, direction $D_i$, and magnitude $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 a line with slope 1 passing through the point $(X_i, 0)$, and the strata in the region above this line move by height $L_i$ along the line. That is, a point $(x, y)$ above this line moves to $(x + L_i, y + L_i)$.
  • When $D_i = 2$, a fault is created along a line with slope $-1$ passing through the point $(X_i, 0)$, and the strata in the region above this line move by height $L_i$ along the line. That is, a point $(x, y)$ above this line moves to $(x - L_i, y + L_i)$.
• Immediately after that, all strata in the region $y > 0$ disappear due to weathering.

Time has passed to the present day, and the archaeologist Dr. JOI has decided to excavate the ruins of the IOI civilization. Dr. JOI wants to know how many years before the IOI civilization perished the stratum at each position on the ground surface was formed. The history of the crustal movements is known. Your task is to act on behalf of Dr. JOI and, for each integer $i$ satisfying $1 \le i \le N$, determine how many years before the IOI civilization perished the stratum on the ground surface between point $(i-1, 0)$ and point $(i, 0)$ was formed.

Input

Read the following from standard input:

• The first line contains two integers $N$ and $Q$, separated by a space. This indicates that the number of points for which the answer is required is $N$, and the number of crustal movements is $Q$.
• The $i$-th line ($1 \le i \le Q$) of the following $Q$ lines contains three integers $X_i, D_i, L_i$, separated by spaces. This indicates that the position of the $i$-th crustal movement is $X_i$, the direction is $D_i$, and the magnitude of the movement is $L_i$.

Output

The output should consist of $N$ lines. The $i$-th line ($1 \le i \le N$) of standard output should contain an integer representing how many years before the IOI civilization perished the stratum on the ground surface between point $(i-1, 0)$ and point $(i, 0)$ was formed.

Constraints

All input data satisfy the following conditions:

• $1 \le N \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le Q$).
• $1 \le D_i \le 2$ ($1 \le i \le Q$).
• $1 \le L_i \le 1\,000\,000\,000$ ($1 \le i \le Q$).

Subtasks

Subtask 1 [18 points]

The following conditions are satisfied: $N \le 100$. $Q \le 100$. $-100 \le X_i \le 100$ ($1 \le i \le Q$). $L_i = 1$ ($1 \le i \le Q$).

Subtask 2 [16 points]

The following conditions are satisfied: $N \le 3\,000$. $Q \le 3\,000$.

Subtask 3 [66 points]

There are no additional constraints.

Examples

Input 1

10 2
12 1 3
2 2 2

Output 1

3
3
5
5
5
5
5
5
2
2

Note

This input example corresponds to the following diagram.

Input 2

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

Output 2

5
5
4
5
5
5
5
5
4
4

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

Output 3

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