거래 Batch 컴파일 명령

지학이가 사는 대전과 승현이가 사는 서울 사이에는 $1$부터 $N$까지의 번호가 붙은 $N$개의 크고 작은 마을들이 있습니다. 겨울이 오면 $M$명의 모자 상인들이 손수 뜨개질한 모자를 팔러 이곳저곳을 돌아다닙니다. 이들은 같은 도시에서 이틀 이상 거래하지 않아야 하고 (즉 매일 방문하지 않았던 다른 도시로 가야 합니다), 모자의 가격을 매일 올려야 합니다.

더 정확히 쓰자면, $i$번째 상인에 대해:

1. $L_{i}$번 마을에서 거래를 시작합니다. 이 때 모자 가격은 $X_{i}$입니다.
2. 매일 바로 다음의 인접한 마을로 이동합니다. 정확히 말하자면, 만약 이 상인이 어제 $j$번 마을에 있었다면, 오늘에는 $j+1$번 마을에서 거래를 하고 있겠네요.
3. 매일 모자의 가격을 $1$만큼 올립니다. 어제 모자의 가격이 $x$였다면, 오늘은 $x+1$이 됩니다.
4. $R_{i}$번 도시에서의 거래가 끝나면 집으로 돌아갑니다.

이를 관망하던 석환이는 각 마을마다 그 마을에서 판매되었던 가장 비싼 모자의 가격을 알고자 합니다.

입력 형식

첫 번째 줄에는 마을의 수 $N$ ($1 \le N \le 300,000$)과 상인의 수 $M$ ($1 \le M \le 300,000$)이 공백을 사이로 두고 주어집니다.

다음 $M$개 줄에는 3개의 정수 출발하는 마을의 번호 $L_{i}$, 마지막으로 거래하는 마을의 번호 $R_{i}$ ($1 \le L_{i} \le R_{i} \le N$), 모자의 최초 가격 $X_{i}$ ($1 \le X_{i} \le 10^{9}$)가 공백을 사이로 두고 주어집니다.

출력 형식

$N$개의 정수를 공백을 사이로 두고 출력합니다. 이 때 $i$번째 숫자는 $i$번 마을에서 판매되었던 가장 비싼 모자의 가격이 되어야 합니다. 단 $i$번 마을에 상인이 아무도 방문하지 않았다면 0을 출력합니다.

예제

예제 1

입력

5 2
1 3 2
2 4 6

출력

2 6 7 8 0

예제 2

입력

6 4
4 4 3
1 2 5
5 6 1
6 6 1

출력

5 6 0 3 1 2