컨베이어 벨트

Awesome Conveyor Machine(ACM)은 Industrial Conveyor Product Corporation(ICPC) 공장에서 가장 중요한 설비다. ACM에는 제품을 한 지점에서 다른 지점으로 옮기는 긴 컨베이어 벨트가 있다. 당신은 효율적인 배송 계획을 세우려고 고용된 프로그래머다.

ACM의 컨베이어 벨트는 같은 간격으로 놓인 $N$개의 지점을 지난다. 벨트 위에는 판이 실려 있고, 판 하나에는 제품을 최대 하나만 올릴 수 있다. 처음에는 어느 지점에도 판이 없다. 벨트는 단위 시간마다 정확히 판 하나의 길이만큼 움직인다. 1초 뒤에는 위치 1에 판이 하나 있고 다른 위치에는 판이 없다. 다시 1초가 지나면 위치 1에 있던 판이 위치 2로 옮겨 가고 위치 1에는 새 판이 들어오며, 이후로도 같은 방식으로 이어진다. 판의 개수에는 제한이 없으므로 $N$초 이후에는 $N$개의 위치마다 판이 정확히 하나씩 놓인다.

배송 작업 하나는 두 위치 $a$와 $b$ ($a < b$)로 나타낸다. 위치 $a$에서 벨트 위의 판에 제품을 올리고, $b - a$초 뒤에 위치 $b$에서 그 제품을 내리면 배송이 끝난다. 물론 제품을 올리는 순간 그 위치에 빈 판이 있어야 한다. 그 밖에 제품을 올리고 내릴 때는 다음 규칙을 지켜야 한다.

• 제품을 올리거나 내리는 순간에는 판이 정확히 그 위치에 있어야 한다. 즉, 제품은 정수 초에만 올리고 내린다.
• 같은 위치에서 제품을 올리는 일과 내리는 일을 동시에 할 수는 없다. 서로 다른 위치라면 올리는 일과 내리는 일을 동시에 해도 된다.

작업이 여러 개라면 각 제품을 벨트에 올리는 시점을 조절해서 모든 작업을 마치는 데 걸리는 시간을 줄일 수도 있다. 당신이 할 일은 모든 작업을 마치는 시간을 최소화하는 프로그램을 작성하는 것이다... 잠깐. 언제부터 모든 작업을 처음부터 다 알 수 있다고 착각한 것인가? 새 배송 요청은 컨베이어 위의 판처럼 시시각각 들어온다. 그러니 새 요청이 들어올 때마다 최적의 계획을 갱신해야 한다.

요청 하나는 출발 지점 $a$, 도착 지점 $b$, 그리고 $a$에서 $b$로 배송할 제품의 개수 $p$로 이루어진다. 요청은 $Q$번 들어온다. 당신의 진짜 일은 $1 \le i \le Q$인 모든 $i$마다 요청 1부터 $i$까지의 배송 작업을 모두 마치는 데 걸리는 최소 시간을 구하는 프로그램을 작성하는 것이다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

N Q
a1 b1 p1
⋮
aQ bQ pQ

첫째 줄에 두 정수 $N$과 $Q$가 주어진다 ($2 \le N \le 10^5$, $1 \le Q \le 10^5$). $N$은 컨베이어 벨트가 지나는 위치의 개수이고 $Q$는 들어오는 요청의 개수다. 이어지는 $Q$개의 줄 중 $i$번째 줄에는 세 정수 $a_i$, $b_i$, $p_i$가 주어진다 ($1 \le a_i < b_i \le N$, $1 \le p_i \le 10^9$). 이는 $i$번째 요청이 위치 $a_i$에서 위치 $b_i$로 제품 $p_i$개를 배송해 달라는 뜻이다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 요청 1부터 $i$까지의 작업을 모두 마치는 데 걸리는 최소 시간을 출력한다. 시간은 벨트가 움직이기 시작한 순간부터 세며, 마지막 제품을 내리는 시각이 곧 완료 시간이다.

첫 번째 예제에서 첫 번째 요청만 처리하는 데 걸리는 최소 시간은 4초다. 두 요청을 모두 처리하는 것도 4초 안에 끝낼 수 있다. 아래 그림을 참고하라.