题目描述

小 G 手里有一个 $0$ 到 $n − 1$ 的排列 $p$，她不肯告诉小 W 具体内容，但允许小 W 多次询问某段区间的最小值。你偷听到了 $q$ 个询问，想还原出这个排列。

如果有多个符合询问结果的排列，可输出任意一个。如果小 G 在欺骗小 W（即不存在这样的排列），需要输出 $n$ 个 $−1$。

输入格式

第一行，两个正整数 $n$ 和 $q$。

接下来 $q$ 行，每行三个整数 $l, r, x$，表示区间 $[l, r]$ 中 $p$ 值最小为 $x$。

输出格式

一行，$n$ 个整数，表示答案，你需要保证每个数都在 $[0, n − 1]$ 内。

样例

样例 1

5 3
0 2 1
1 3 0
1 4 0

1 4 3 0 2

样例 2

3 2
0 1 1
1 2 1

-1 -1 -1

数据范围

• 子任务 $1$，分值 $23$ 分，保证 $n, q \le 10$。
• 子任务 $2$，分值 $44$ 分，保证 $n,q\le 10^3$。
• 子任务 $3$，分值 $33$ 分，保证 $n,q\le 10^5$。

注意：如果你无法判断最终答案是否为 $-1$，并且输出的是一个符合条件的数列，但不是 $0$ 到 $n − 1$ 的排列，可以获得该子任务 $30\%$ 的分数。例如在样例 $2$ 中，输出 1 1 1 可获得这一部分分。