CF356A.Knight Tournament

Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate in this grand event.

As for you, you're just a simple peasant. There's no surprise that you slept in this morning and were late for the tournament (it was a weekend, after all). Now you are really curious about the results of the tournament. This time the tournament in Berland went as follows:

• There are n knights participating in the tournament. Each knight was assigned his unique number — an integer from 1 to n.
• The tournament consisted of m fights, in the i-th fight the knights that were still in the game with numbers at least l__i and at most r__i have fought for the right to continue taking part in the tournament.
• After the i-th fight among all participants of the fight only one knight won — the knight number x__i, he continued participating in the tournament. Other knights left the tournament.
• The winner of the last (the m-th) fight (the knight number x__m) became the winner of the tournament.

You fished out all the information about the fights from your friends. Now for each knight you want to know the name of the knight he was conquered by. We think that the knight number b was conquered by the knight number a, if there was a fight with both of these knights present and the winner was the knight number a.

Write the code that calculates for each knight, the name of the knight that beat him.

太好了！贝尔兰国王贝尔二世正在举办一场骑士锦标赛。国王已经向王国中所有骑士发出了参赛通知，而他们也都欣然接受了这一盛事的邀请。

至于你，只不过是一名普通的农民。不出所料，今天早上你睡过头了，因而错过了锦标赛（毕竟这是周末）。现在你对锦标赛的结果非常好奇。本次贝尔兰锦标赛的赛制如下：

• 共有 $n$ 名骑士参加锦标赛。每位骑士被分配了一个唯一的编号——一个从 $1$ 到 $n$ 的整数。
• 锦标赛共进行了 $m$ 场对决；在第 $i$ 场对决中，所有当时仍在锦标赛中、且编号在区间 $[l_i, r_i]$ 内的骑士均参与了这场对决，以争夺继续留在锦标赛中的资格。
• 在第 $i$ 场对决的所有参与者中，仅有一名骑士获胜——即编号为 $x_i$ 的骑士；他得以继续参加后续比赛，其余所有参与该场对决的骑士则退出锦标赛。
• 最后一场（即第 $m$ 场）对决的获胜者（编号为 $x_m$ 的骑士）成为整个锦标赛的冠军。

你已从朋友们那里打探到了全部对决的信息。现在，你需要对每一位骑士，找出击败他的那位骑士的编号。我们定义：若存在某场对决，其中编号为 $a$ 和 $b$ 的两位骑士同时参与，且该场对决的获胜者是编号为 $a$ 的骑士，则称骑士 $b$ 被骑士 $a$ 击败。

请编写程序，对每位骑士，输出击败他的那位骑士的编号。

The first line contains two integers n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) — the number of knights and the number of fights. Each of the following m lines contains three integers l__i, r__i, x__i (1 ≤ l__i < r__i ≤ n; l__i ≤ x__i ≤ r__i) — the description of the i-th fight.

It is guaranteed that the input is correct and matches the problem statement. It is guaranteed that at least two knights took part in each battle.

第一行包含两个整数 $n$、$m$（$2 \leq n \leq 3\cdot10^5$；$1 \leq m \leq 3\cdot10^5$）—— 分别表示骑士的数量和战斗的次数。接下来的 $m$ 行中，每行包含三个整数 $l_i$、$r_i$、$x_i$（$1 \leq l_i < r_i \leq n$；$l_i \leq x_i \leq r_i$）—— 描述第 $i$ 场战斗。

保证输入数据合法且符合题目描述。保证每场战斗中至少有两名骑士参与。

Print n integers. If the i-th knight lost, then the i-th number should equal the number of the knight that beat the knight number i. If the i-th knight is the winner, then the i-th number must equal 0.

输出 n 个整数。如果第 i 位骑士失败了，则第 i 个数应等于击败第 i 位骑士的那位骑士的编号；如果第 i 位骑士是获胜者，则第 i 个数必须为 0。

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.

考虑第一个测试用例。骑士 1 和骑士 2 进行了第一场决斗，骑士 1 获胜；骑士 1 和骑士 3 进行了第二场决斗，骑士 3 获胜；最后一场决斗在骑士 3 和骑士 4 之间进行，骑士 4 获胜。