Conveyor Belt

Awesome Conveyor Machine (ACM) is the most important piece of equipment in a factory of Industrial Conveyor Product Corporation (ICPC). ACM has a long conveyor belt that carries products from some points to other points. You are a programmer hired to plan an efficient delivery schedule.

ACM's conveyor belt passes through $N$ points at equal intervals. The belt carries plates, and each plate holds at most one product. Initially there is no plate at any point. The belt moves exactly one plate length per unit of time: after one second a plate is at position 1 and no other position has a plate. One second later, the plate at position 1 has moved to position 2 and a new plate has arrived at position 1, and so on. The number of plates is unlimited, so from $N$ seconds on, each of the $N$ positions holds exactly one plate.

A delivery task is given by two positions $a$ and $b$ ($a < b$). It is completed by putting a product on a plate at position $a$ and taking the product off at position $b$, $b - a$ seconds later. Of course, an empty plate has to be at position $a$ at the moment the product is put on. Putting on and taking off also follow these rules.

• At the moment a product is put on or taken off, a plate must be exactly at that position. That is, products are put on and taken off only at integer seconds.
• Putting a product on and taking a product off at the same position cannot happen at the same time. Putting on and taking off at different positions may happen at the same time.

With several tasks, choosing when each product is put on the belt can reduce the time needed to finish them all. Your job is to write a program that minimizes the time to complete every task... wait. Since when did you assume that you know all the tasks in advance? New delivery requests keep arriving one after another, like plates on the conveyor. So you have to update the optimal schedule after 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$. Requests arrive $Q$ times. Your real job is to write a program that, for each $i$ with $1 \le i \le Q$, finds the minimum time to complete every delivery task in requests 1 to $i$.

The input is a single test case in the following format.

N Q
a1 b1 p1
⋮
aQ bQ pQ

The first line has two integers $N$ and $Q$ ($2 \le N \le 10^5$, $1 \le Q \le 10^5$): $N$ is the number of positions the belt passes through and $Q$ is the number of requests. The $i$-th of the following $Q$ lines has three integers $a_i$, $b_i$, and $p_i$ ($1 \le a_i < b_i \le N$, $1 \le p_i \le 10^9$), meaning that the $i$-th request asks for $p_i$ products to be delivered from position $a_i$ to position $b_i$.

Print $Q$ lines. On the $i$-th line, print the minimum time to complete all tasks of requests 1 to $i$. Time is counted from the moment the belt starts moving, and the completion time is the second at which the last product is taken off.

In the first sample, the minimum time to complete only the first request is 4 seconds, and both requests can also be completed within 4 seconds. See the figure below.