Problem Background

The score for this problem is set according to the original COCI configuration, with a maximum score of $140$.

Problem Description

Mirko is bored, so he takes a piece of paper and writes down a sequence \( A \) containing \( N \) elements, where all integers from \( 1 \) to \( N \) appear exactly once. Then, he takes another piece of paper and writes down \( M \) descriptions about \( A \).

Each description can be one of two types:

• 1 x y v: Indicates that the largest number in the interval \([x, y]\) is \( v \).
• 2 x y v: Indicates that the smallest number in the interval \([x, y]\) is \( v \).

Slavko then comes along and steals his first piece of paper. Mirko is desperate and wants you to find a sequence that satisfies these descriptions, which does not necessarily have to be identical to the original sequence.

Input Format

The first line contains two integers \( N \) and \( M \) \((1 \le N \le 200, 0 \le M \le 4 \times 10^4)\), representing the length of the sequence and the number of descriptions, respectively.

The next \( M \) lines each contain a description.

Output Format

Output a single line containing a sequence of length \( N \) that satisfies all the descriptions, with each number from \( 1 \) to \( N \) appearing exactly once, separated by spaces. If no such sequence exists, output \(-1\).

Sample Input and Output

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

见题面 Input 部分

见题面 Output 部分