Mex
题目背景
忘掉种过的花/重新的出发/放弃理想吧。
题目描述
小 G 曾经有一个 $0$ 到 $n$ 的排列(下标从 $0$ 开始),但他忘记了这个排列。
现在他想把这个排列找回来,他努力地回想,只能回想起关于这个排列的 $m$ 条信息,每条信息形如 $(l,r,val)$,表示区间 $[l,r]$ 的 ${\rm mex}$ 值为 $val$。一个区间的 ${\rm mex}$ 值是最小的没有在这个区间中出现的自然数。
小 G 把 $n$ 和这 $m$ 条信息告诉了你,希望你能帮他还原出一个排列,或者告诉他他的回忆出现了问题。
输入输出格式
输入格式
第一行两个整数 $n$ 和 $m$,含义见上。
随后 $m$ 行每行三个整数 $l,r,val$ 描述一条信息,表示区间 $[l,r]$ 的 ${\rm mex}$ 值为 $val$。
输出格式
如果不存在满足所有条件的排列,输出 $-1$。
否则输出一行 $n+1$ 个正整数,表示一个 $0$ 到 $n$ 的排列。
**本题采用 Special Judge**。如果满足条件的排列有多个,你可以输出任意一个。
输入输出样例
输入样例 #1
3 4
0 0 0
0 1 1
0 2 2
1 3 3
输出样例 #1
3 0 1 2
输入样例 #2
5 7
0 1 0
4 5 0
1 3 1
0 5 6
0 5 6
2 5 3
2 3 1
输出样例 #2
4 3 5 0 1 2
说明
**本题采用捆绑测试**。你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。
- Subtask 1(15 points):$n,m\le 10$;
- Subtask 2(20 points):$n,m\le 20$;
- Subtask 3(10 points):$val=0$;
- Subtask 4(15 points):数据随机生成;
- Subtask 5(10 points):$n\le 10^5$;
- Subtask 6(30 points):无特殊限制。
对于所有的数据满足:$1 \le n,m\le 5\times 10^5$,$ 0\le l,r\le n$,$0\le val\le n+1$。
Subtask4 的数据生成方式为:随机生成一个排列,再随机 $m$ 个区间求出它们的 ${\rm mex}$ 值作为条件。
本题输入输出量较大,请注意使用效率较高的 IO 方式。