题目描述

欢呼！ 伯兰国的国王正在举办一场骑士锦标赛。国王已经向王国中的所有骑士发出了消息，他们也都同意参加这一盛事。

至于你，只是一个普通的平民。今天早上你睡过头了，错过了锦标赛（毕竟今天是周末）。现在你对锦标赛的结果非常好奇。这次伯兰国的锦标赛规则如下：

有 $n$ 名骑士参加锦标赛。每名骑士都被分配了一个唯一的编号—从 $1$ 到 $n$ 的整数。 锦标赛由 $m$ 场战斗组成，在第 $i$ 场战斗中，编号至少为 $l_i$ 且至多为 $r_i$ 的仍在游戏中的骑士们为了继续参加锦标赛的权利而战。 在第 $i$ 场战斗之后，所有参与这场战斗的骑士中只有一名骑士获胜—编号为 $x_i$ 的骑士，他将继续参加锦标赛。其他骑士则被淘汰出局。 最后一场（第 $m$ 场）战斗的胜者（编号为 $x_m$ 的骑士）成为锦标赛的冠军。 你从朋友那里得到了所有战斗的信息。现在，你想知道每位骑士是被哪位骑士打败的。我们认为，如果骑士 $b$ 和骑士 $a$ 在同一场战斗中，并且骑士 $a$ 获胜，那么可以说骑士 $b$ 被骑士 $a$ 打败了。

输入格式

第一行包含两个整数 $n$, $m$—骑士的数量和战斗的数量。

接下来的 $m$ 行，每行包含三个整数 $l_i$, $r_i$, $x_i$—第 $i$ 场战斗的描述。

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

输出格式

输出 $n$ 个整数。如果第 $i$ 名骑士输了，那么第 $i$ 个数字应等于打败他的骑士的编号。如果第 $i$ 名骑士最后赢了，那么第 $i$ 个数字为为 $0$。

样例

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 

数据范围

• $2 \leq n \leq 3\times10^5$
• $1 \leq m \leq 3 \times 10^5$
• $1 \leq l_i < r_i \leq n, 1 \leq x_i \leq r_i$