题目描述

好消息！Berland 国王 Berl II 决定举办一场盛大的骑士锦标赛，并已经召集全国骑士参加。你只是一名普通农夫，周末睡过了头，等赶到赛场时比赛已经结束，只能从朋友那里收集每一场战斗的记录。

锦标赛共有 $n$ 名骑士，他们的编号互不相同，依次为 $1$ 到 $n$。比赛一共进行 $m$ 场。第 $i$ 场战斗开始时，所有仍未出局且编号处于区间 $[l_i,r_i]$ 内的骑士都会参战。该场只有编号为 $x_i$ 的骑士获胜并继续留在比赛中，其余参战骑士全部被 $x_i$ 击败并永久退出后续比赛。最后一场的胜者同时成为整场锦标赛的冠军。

若骑士 $a$ 与骑士 $b$ 同时参加某场战斗，并且该场胜者是 $a$，就称骑士 $b$ 被骑士 $a$ 击败。请根据按时间排列的战斗记录，确定每一名骑士最终是被谁击败的；最终冠军没有击败者。

输入格式

第一行包含两个整数 $n,m$，分别表示骑士数和战斗场数。

接下来 $m$ 行，每行包含三个整数 $l_i,r_i,x_i$，表示第 $i$ 场战斗由当时仍在比赛中且编号位于 $[l_i,r_i]$ 的骑士参加，唯一胜者为 $x_i$。

输入保证记录合法，并且每一场战斗至少有两名尚未出局的骑士参加。

输出格式

输出 $n$ 个整数。若第 $i$ 名骑士落败，则第 $i$ 个整数为击败他的骑士编号；若第 $i$ 名骑士是最终冠军，则第 $i$ 个整数为 $0$。

4 3
1 2 1
1 3 3
1 4 4

3 1 4 0

样例说明 #1

骑士 $2$ 被 $1$ 击败，之后 $1$ 被 $3$ 击败，最后 $3$ 被 $4$ 击败。

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

0 8 4 6 4 8 6 1

2 1
1 2 2

2 0

样例说明 #3

两名骑士进行唯一一场比赛，编号 $2$ 的骑士成为冠军。

数据范围与约定

$2\le n\le 3\times 10^5$，$1\le m\le 3\times 10^5$，$1\le l_i<r_i\le n$，$l_i\le x_i\le r_i$。全部战斗记录与比赛过程相符。