← 返回题目列表

Codeforces · 356/A

A. 骑士锦标赛

中文机器翻译题面 查看原题

万岁!贝尔兰国王贝尔二世正在举办一场骑士锦标赛。国王已经向王国所有的骑士发出了消息,他们也都同意参加这次盛会。

至于你,你只是一个普通的农民。毫不奇怪,你今天早上睡了,比赛迟到了(毕竟这是一个周末)。现在你真的很好奇锦标赛的结果。这次在伯兰举行的比赛如下:

- 有 n 位骑士参加比赛。每个骑士都被分配了一个唯一的编号——一个从 1 到 n 的整数。
- 锦标赛共有 m 场比赛,在第 i 场比赛中,仍在比赛中人数最少为 li、最多为 ri 的骑士已争夺继续参加比赛的权利。
- 在所有参加者的第 i 次战斗之后,只有一名骑士获胜 - 骑士号 xi,他继续参加比赛。其他骑士退出了比赛。
- 最后(第 m)场比赛的获胜者(骑士编号 xm)成为锦标赛的获胜者。

你从你的朋友那里找出了所有关于打架的信息。现在,对于每个骑士,您想知道他被征服的骑士的名字。如果双方都在场的情况下发生战斗,并且胜利者是a号骑士,我们认为b号骑士被a号骑士征服了。

编写计算每个骑士的代码,计算击败他的骑士的名字。

输入

第一行包含两个整数 n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) — 骑士数量和战斗次数。以下 m 行中的每一行包含三个整数 li、ri、xi (1 ≤ li < ri ≤ n; li ≤ xi ≤ ri) — 第 i 场战斗的描述。

保证输入正确且与问题陈述相符。保证每场战斗至少有两名骑士参加。

输出

打印 n 个整数。如果第i个骑士输了,那么第i个数字应该等于击败第i个骑士的骑士的数字。如果第 i 个骑士获胜,则第 i 个数字必须等于 0。

示例

输入 #1

4 3
1 2 1
1 3 3
1 4 4

输出 #1

3 1 4 0

输入 #2

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

输出 #2

0 8 4 6 4 8 6 1

注意

考虑第一个测试用例。骑士1和骑士2进行了第一场战斗,骑士1获胜。骑士1和骑士3进行了第二场战斗,骑士3获胜。最后一场比赛是骑士3和骑士4之间,骑士4获胜。