컨베이어 벨트

문제

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초 안에 끝낼 수 있다. 아래 그림을 참고하라.