No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一个数组 a，长度为 n，最开始数组的所有元素都没有颜色。接下来你要发挥自己的想象力，把数组涂上好看的颜色。

颜色最多有 n 种，将颜色简单表示成整数，即 1,2,3,...,n−1,n。将进行 m 次涂色，每次涂色会选择一个区间 [l,r]，将这个区间的所有元素涂成颜色 color（之前涂过的颜色会被覆盖）。当涂色完成后，请从 1 ~ n 按顺序输出每个元素当前的颜色，若元素 ai 没有颜色则 ai=0。

Format

Input

第一行包含正整数 n 和 m，用空格隔开，表示数组长度和小码君涂色的次数。

接下来 m 行，每行输入为 l r color，表示将区间 [l,r] 涂成颜色 color。

Output

输出 n 个整数，用空格隔开，表示数组每个元素的颜色。

Samples

5 3
1 3 5
2 4 6
5 5 7

5 6 6 6 7

5 4
1 4 6
1 3 5

5 5 5 6 0

Limitation

对于 50% 的数据，1≤n,m≤1000

对于 100% 的数据，1≤n,m≤200000

1s, 1024KiB for each test case.