Description

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.

Input Format

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$.

Output Format

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.

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 

Hint

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