Description

万岁！Berl II，Berland国王正在举办一场骑士锦标赛。国王已经向王国中的所有骑士发出了邀请，他们也纷纷同意参加这一盛大活动。

而你，只是一个普通的农民。毫无意外，你今天早上睡过头了，错过了锦标赛（毕竟是周末嘛）。现在你非常好奇锦标赛的结果。这次Berland的锦标赛如下进行：

• 有n名骑士参加了锦标赛。每个骑士都被分配了一个独一无二的编号 — 从1到n的整数。
• 锦标赛包括m场比赛，在第i场比赛中，编号至少为l~i~且至多为r~i~的骑士将为继续参加锦标赛而进行战斗。
• 在第i场比赛中，所有参与者中只有一名骑士获胜 — 编号为x~i~的骑士，他继续参加锦标赛。其他骑士离开了比赛。
• 最后一场比赛（第m场）的获胜者（编号为xm的骑士）成为了锦标赛的冠军。

你从朋友那里打听到了所有比赛的信息。现在你想知道每个骑士被哪个骑士打败了。我们认为骑士编号为b的骑士被编号为a的骑士打败了，如果有一场比赛中这两名骑士都参与，并且获胜的是编号为a的骑士。

编写代码，计算每个骑士被谁打败了。

输入

第一行包含两个整数n，m (2 ≤ n ≤ 3·10​^5​; 1 ≤ m ≤ 3·10​^5​) — 骑士的数量和比赛的次数。接下来的m行中，每行包含三个整数li, ri,xi(1 ≤ li< ri ≤ ​n​; li ≤ xi ≤ ri) — 第i场比赛的描述。

保证输入是正确的，并与问题描述相匹配。保证每场战斗中至少有两名骑士参与。

输出

打印n个整数。如果第i名骑士失败了，那么第i个数字应该等于打败骑士编号为i的骑士的编号。如果第i名骑士是获胜者，那么第i个数字必须等于0。

Samples

4 3
1 2 1
1 3 3
1 4 4

3 1 4 0

8 4
3 5 4
3 7 6
2 8 8
1 8 1

0 8 4 6 4 8 6 1

Note

Consider the first test case. Knights 1 and 2 fought the first fight and knight 1 won. Knights 1 and 3 fought the second fight and knight 3 won. The last fight was between knights 3 and 4, knight 4 won.