벽 칠하기II

경곽이는 이번에 학교 벽에 페인트를 칠하려고 한다. 벽은 다음 그림과 같이 조각으로 구성되어 있다. 페인트 색은 고유한 번호를 가진다.

경곽이는 조금 변덕이 심해서 벽의 일부구간에 색을 칠하고 감상을 하다가 다시 벽의 일정구간을 또 다른 색으로 칠하기를 반복하였다. 마침내 경곽이가 벽의 색칠하기를 완료한 후 벽의 색칠 상태를 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 벽의 조각 수 n과 벽에 색칠하기의 반복 횟수 m이 입력된다.

두 번째 줄에 1부터 m까지의 벽의 폐구간 [a, b]와 페인트의 색 번호 c가 공백으로 구분되어 입력된다.

[입력값의 정의역]

1 <= n, m, c <= 100,000,  a <= b,

Output

벽에 최종적으로 칠해진 페인트 색의 번호를 공백으로 구분하여 출력한다. 단, 벽에 색이 칠해지지 않은 경우는 0으로 출력한다.

IO Example

입력1

5 3

1 3 1

2 3 2

4 4 1

출력

1 2 2 1 0

* 페인트를 칠하는 과정은 1 1 1 0 0  →  1 2 2 0 0  →  1 2 2 1 0 로 변경되며 최종적으로 벽의 색은 1 2 2 1 0의 상태가 된다.

입력2

8 7

1 3 1

2 6 2

4 7 3

6 8 4

2 8 5

1 6 6

1 2 7

출력

7 7 6 6 6 6 5 5