Mirko was bored, so he took a piece of paper and wrote down a sequence of length , which contains each positive integer between and , inclusive, exactly once. After that, he took another piece of paper and wrote down descriptions of the sequence .
Each description has one of the following formats:
1 x y v
- the largest number in positions between and (inclusive) equals
2 x y v
- the smallest number in positions between and (inclusive) equals
Then Slavko came, saw, and stole the first paper. Mirko is desperate and has asked you to find some sequence matching the descriptions, not necessarily equal to the original sequence.
Input Specification
The first line of input contains two positive integers, , the length of the sequence, and , the number of descriptions.
Each of the following lines contains a description as described above.
Output Specification
The first and only line of output must contain a sequence of space-separated positive integers (matching the descriptions and containing all positive integers from to ), or -1
if no such sequence exists.
Sample Input 1
3 2
1 1 1 1
2 2 2 2
Sample Output 1
1 2 3
Sample Input 2
4 2
1 1 1 1
2 3 4 1
Sample Output 2
-1
Sample Input 3
5 2
1 2 3 3
2 4 5 4
Sample Output 3
1 2 3 4 5
Comments