题目背景

译自 NOISG 2017 D.RMQ。

题目描述

小 K 有 $N$ 头奶牛，编号分别为 $0$ 至 $N-1$。这些奶牛以某种未知的顺序排成了一排。

现在给出 $Q$ 条信息，每条信息包含三个整数 $L_i,R_i,A_i$，表示区间 $[L_i,R_i]$ 内编号最小的奶牛的编号为 $A_i$。请你构造一组奶牛的顺序使得其可以满足所有信息。

输入格式

第一行两个正整数 $N,Q$，分别表示奶牛数和信息数。

接下来 $Q$ 行，每行三个整数 $L_i,R_i,A_i$，代表一条信息。

输出格式

一行 $N$ 个整数表示你构造的奶牛的顺序。如果有多个解，输出任意一个即可。如果无解，输出 $N$ 个 $-1$。

5 3
0 2 1
1 3 0
1 4 0

1 4 3 0 2

3 2
0 1 1
1 2 1

-1 -1 -1

提示

样例解释

对于样例 1，请注意这不是唯一满足要求的顺序。

对于样例 2，如果 $0$ 号奶牛在 $0$ 号位置或者 $1$ 号位置，那么区间 $[0,1]$ 的最小值应为 $0$ 而非 $1$；如果 $0$ 号奶牛在 $2$ 号位置，那么区间 $[1,1]$ 的最小值应为 $0$ 而非 $1$。因此，不存在符合要求的顺序。

评分标准

对于一个测试点：

• 如果你的输出满足以下要求，你将获得该测试点所有的分数：
  • 输出 $N$ 个数。
  • 该测试点无解，并且你也判断无解。
  • 该测试点有解，并且你构造的顺序满足所有信息而且没有奶牛编号相同。
• 如果你的输出满足以下要求，你将获得该测试点 $30\%$ 的分数：
  • 输出 $N$ 个数。
  • 你构造的顺序满足所有信息但是有奶牛编号相同。
• 否则你将获得该测试点 $0\%$ 的分数。

例如，对于样例 2，如果你输出 1 1 1，那么你将获得该点 $30\%$ 的分数。

数据范围

本题采用 $\text{Subtask}$ 捆绑测试。

对于所有数据，保证 $1\le N,Q\le10^5$，$0\le L_i,R_i< N$，$0\le A_i< N$。