Conveyor Belt

Awesome Conveyor Machine (ACM) is the most important equipment of a factory of Industrial Conveyor Product Corporation (ICPC). ACM has a long conveyor belt to deliver their products from some points to other points. You are a programmer hired to make efficient schedule plan for product delivery.

ACM's conveyor belt goes through $N$ points at equal intervals. The conveyor has plates on each of which at most one product can be put. Initially, there are no plates at any points. The conveyor belt moves by exactly one plate length per unit time; after one second, a plate is at position 1 while there are no plates at the other positions. After further 1 seconds, the plate at position 1 is moved to position 2 and a new plate comes at position 1, and so on. Note that the conveyor has the unlimited number of plates: after $N$ seconds or later, each of the $N$ positions has exactly one plate.

A delivery task is represented by positions $a$ and $b$; delivery is accomplished by putting a product on a plate on the belt at $a$, and retrieving it at $b$ after $b - a$ seconds ($a < b$). (Of course, it is necessary that an empty plate exists at the position at the putting time.) In addition, putting and retrieving products must bedone in the following manner:

• When putting and retrieving a product, a plate must be located just at the position. That is, products must be put and retrieved at integer seconds.
• Putting and retrieving at the same position cannot be done at the same time. On the other hand, putting and retrieving at the different positions can be done at the same time.

If there are several tasks, the time to finish all the tasks may be reduced by changing schedule when each product is put on the belt. Your job is to write a program minimizing the time to complete all the tasks... wait, wait. When have you started misunderstanding that you can know all the tasks initially? New delivery requests are coming moment by moment, like plates on the conveyor! So you should update your optimal schedule per every new request.

A request consists of a start point $a$, a goal point $b$, and the number $p$ of products to deliver from $a$ to $b$. Delivery requests will be added $Q$ times. Your (true) job is to write a program such that for each $1 \leq i \leq Q$, minimizing the entire time to complete delivery tasks in requests 1 to $i$.

Input

The input consists of a single test case formatted as follows.

$N$ $Q$ $a_1$ $b_1$ $p_1$ : $a_Q$ $b_Q$ $p_Q$

A first line includes two integers $N$ and $Q$ ($2 \leq N \leq 10^5, 1 \leq Q \leq 10^5$): $N$ is the number of positions the conveyor belt goes through and $Q$ is the number of requests will come. The $i$-th line of the following $Q$ lines consists of three integers $a_i, b_i,$ and $p_i$ ($1 \leq a_i < b_i \leq N, 1 \leq p_i \leq 10^9$), which mean that the $i$-th request requires $p_i$ products to be delivered from position $a_i$ to position $b_i$.

Output

In the $i$-th line, print the minimum time to complete all the tasks required by requests $1$ to $i$.

Examples

Input

5 2 1 4 1 2 3 1

Output

4 4

Input

5 2 1 4 1 2 3 5

Output

4 8

Input

5 2 1 3 3 3 5 1

Output

5 6

Input

10 4 3 5 2 5 7 5 8 9 2 1 7 5

Output

6 11 11 16

inputFormat

Input

The input consists of a single test case formatted as follows.

$N$ $Q$ $a_1$ $b_1$ $p_1$ : $a_Q$ $b_Q$ $p_Q$

A first line includes two integers $N$ and $Q$ ($2 \leq N \leq 10^5, 1 \leq Q \leq 10^5$): $N$ is the number of positions the conveyor belt goes through and $Q$ is the number of requests will come. The $i$-th line of the following $Q$ lines consists of three integers $a_i, b_i,$ and $p_i$ ($1 \leq a_i < b_i \leq N, 1 \leq p_i \leq 10^9$), which mean that the $i$-th request requires $p_i$ products to be delivered from position $a_i$ to position $b_i$.

outputFormat

Output

In the $i$-th line, print the minimum time to complete all the tasks required by requests $1$ to $i$.

Examples

Input

5 2 1 4 1 2 3 1

Output

4 4

Input

5 2 1 4 1 2 3 5

Output

4 8

Input

5 2 1 3 3 3 5 1

Output

5 6

Input

10 4 3 5 2 5 7 5 8 9 2 1 7 5

Output

6 11 11 16

样例

5 2
1 4 1
2 3 1

4
4

</p>