#P6852. Mex

Mex

题目背景

忘掉种过的花/重新的出发/放弃理想吧。

题目描述

小 G 曾经有一个 00nn 的排列(下标从 00 开始),但他忘记了这个排列。

现在他想把这个排列找回来,他努力地回想,只能回想起关于这个排列的 mm 条信息,每条信息形如 (l,r,val)(l,r,val),表示区间 [l,r][l,r]mex{\rm mex} 值为 valval。一个区间的 mex{\rm mex} 值是最小的没有在这个区间中出现的自然数。

小 G 把 nn 和这 mm 条信息告诉了你,希望你能帮他还原出一个排列,或者告诉他他的回忆出现了问题。

输入格式

第一行两个整数 nnmm,含义见上。

随后 mm 行每行三个整数 l,r,vall,r,val 描述一条信息,表示区间 [l,r][l,r]mex{\rm mex} 值为 valval

输出格式

如果不存在满足所有条件的排列,输出 1-1

否则输出一行 n+1n+1 个正整数,表示一个 00nn 的排列。

本题采用 Special Judge。如果满足条件的排列有多个,你可以输出任意一个。

3 4
0 0 0
0 1 1
0 2 2
1 3 3
3 0 1 2
5 7
0 1 0
4 5 0
1 3 1
0 5 6
0 5 6
2 5 3
2 3 1
4 3 5 0 1 2 

提示

本题采用捆绑测试。你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。

  • Subtask 1(15 points):n,m10n,m\le 10
  • Subtask 2(20 points):n,m20n,m\le 20
  • Subtask 3(10 points):val=0val=0
  • Subtask 4(15 points):数据随机生成;
  • Subtask 5(10 points):n105n\le 10^5
  • Subtask 6(30 points):无特殊限制。

对于所有的数据满足:1n,m5×1051 \le n,m\le 5\times 10^50l,rn 0\le l,r\le n0valn+10\le val\le n+1

Subtask4 的数据生成方式为:随机生成一个排列,再随机 mm 个区间求出它们的 mex{\rm mex} 值作为条件。

本题输入输出量较大,请注意使用效率较高的 IO 方式。