4119. 今我来思(sì)

单点时限: 2.0 sec

内存限制: 512 MB

小 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

样例

Input
5 3
0 2 1
1 3 0
1 4 0
Output
1 4 3 0 2
Input
3 2
0 1 1
1 2 1
Output
-1 -1 -1

提示

子任务 $1$,分值 23 分,保证 $n,q\le 10$

子任务 $2$,分值 $44$ 分,保证 $n,q\le 1000$

子任务 $3$,分值 $33$ 分,保证 $n,q\le 100000$

56 人解决,329 人已尝试。

73 份提交通过,共有 1150 份提交。

6.7 EMB 奖励。

创建: 9 月,3 周前.

修改: 8 月,3 周前.

最后提交: 2 月,2 周前.

来源: N/A

题目标签