Kraw 有 $N$ 头奶牛。每头奶牛都戴着一个写有独一无二编号的标签，编号范围为 $0$ 到 $N - 1$。这些奶牛按某种未知的顺序排成一排。奶牛的位置从左到右依次标记为 $0$ 到 $N - 1$。

出于我们可能永远无法得知的原因，Kraw 需要回答多到令人尴尬的区间最小值查询（RMQ）。RMQ 是形如“在位置 $L$ 和 $R$ 之间（包含端点）的奶牛中，最小的标签编号是多少？”的问题。

Kraw 非常懒，所以他以低于最低工资的报酬雇佣了代码猴 Coco 来帮他解决这些 RMQ。Coco 在截止日期前四分钟完成了所有工作，Kraw 非常高兴。

那是 2013 年的事了。现在，Kraw 的奶牛贴标集团正面临巨大亏损，他开始怀疑 Coco 工作的真实性。据他所知，Coco 可能只是随机生成了所有 RMQ 的答案。

不幸的是，这么多年过去了，所有的奶牛都已经散去，而 Coco 也离奇地失联了。请帮助 Kraw 检查是否存在一种奶牛的排列顺序，使得 Coco 的所有答案都是合法的。

输入格式

输入从标准输入读取。输入包含：

• 第一行包含两个整数 $N$（$1 \le N \le 100\,000$），表示奶牛的数量，以及 $Q$（$1 \le Q \le 100\,000$），表示 RMQ 的数量；
• 接下来的 $Q$ 行，其中第 $i$ 行包含三个整数：$L_i$ 和 $R_i$（$0 \le L_i \le R_i < N$），表示第 $i$ 个 RMQ 的左右边界，以及 $A_i$（$0 \le A_i < N$），表示 Coco 对该 RMQ 的答案。

输出格式

输出一行，包含 $N$ 个空格分隔的整数：任意一种可能的奶牛排列顺序，使得对于所有的 $i$，$A_i$ 都是 RMQ $[L_i, R_i]$ 的正确答案，且没有两头奶牛拥有相同的标签编号。

如果不存在任何这样的奶牛排列，则输出 $N$ 个 $-1$。

子任务

每个测试点的最大运行时间为 1.0s。你的程序将在满足以下限制的输入实例集上进行测试：

对于每个测试用例，如果你的程序输出不是一个排列（即包含重复的标签编号），但满足所有的 RMQ，你仍可获得该子任务 30% 的分数。

样例

输入样例 1

5 3
0 2 1
1 3 0
1 4 0

输出样例 1

1 4 3 0 2

说明 1

注意，这并不是唯一会被接受的输出。

首先，我们注意到我们给出的顺序 $[1, 4, 3, 0, 2]$ 确实是一个排列（即 $0$ 到 $4$ 的每个整数都恰好出现一次）。然后，我们检查 RMQ：

• 第一个 RMQ（$L = 0, R = 2$）对应子数组 $[1, 4, 3]$。该区间内的最小标签编号为 $1$。
• 第二个 RMQ 对应子数组 $[4, 3, 0]$。该区间内的最小标签编号为 $0$。
• 第三个 RMQ 对应子数组 $[4, 3, 0, 2]$。该区间内的最小标签编号为 $0$。

由于所有答案都与 Coco 的答案一致，因此 $[1, 4, 3, 0, 2]$ 确实是一个合法的解。

输入样例 2

3 2
0 1 1
1 2 1

输出样例 2

-1 -1 -1

说明 2

如果第 $0$ 头奶牛在位置 $0$ 或 $1$，那么第一个 RMQ 的答案将是 $0$ 而不是 $1$。如果第 $0$ 头奶牛在位置 $2$，那么第二个 RMQ 的答案将是 $0$ 而不是 $1$。因此，无法对奶牛进行排序以满足所有的 RMQ。

注意，以下输出仍可获得该子任务 30% 的分数：

1 1 1