P6852 Mex

Forget the flowers you once planted / set off again / give up on your dreams.

Little G once had a permutation of $0$ to $n$ (indices start from $0$), but he forgot this permutation. Now he wants to recover it. After trying hard to remember, he can only recall $m$ pieces of information about the permutation. Each piece of information is in the form $(l,r,val)$, meaning that the ${\rm mex}$ value of the interval $[l,r]$ is $val$. The ${\rm mex}$ value of an interval is the smallest natural number that does not appear in this interval. Little G tells you $n$ and these $m$ pieces of information, hoping you can help him restore a permutation, or tell him that something is wrong with his memory.

The first line contains two integers $n$ and $m$, with the meanings described above. The next $m$ lines each contain three integers $l,r,val$ describing one piece of information, meaning that the ${\rm mex}$ value of the interval $[l,r]$ is $val$.

If there is no permutation that satisfies all conditions, output $-1$. Otherwise, output one line with $n+1$ positive integers, representing a permutation of $0$ to $n$. **This problem uses Special Judge**. If there are multiple permutations that satisfy the conditions, you may output any one of them.

**This problem uses bundled tests**. You can only get the score of a subtask if you pass all test points in that 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): the testdata is randomly generated. - Subtask 5 (10 points): $n\le 10^5$. - Subtask 6 (30 points): no special constraints. For all testdata: $1 \le n,m\le 5\times 10^5$, $ 0\le l,r\le n$, $0\le val\le n+1$. The testdata generation method for Subtask 4 is: randomly generate a permutation, then randomly choose $m$ intervals and compute their ${\rm mex}$ values as constraints. The input and output sizes are large, so please use an efficient I/O method. Translated by ChatGPT 5