Background

The score for this problem follows the original COCI settings, with a full score of $140$.

Problem Description

Mirko is very bored, so he picks up a sheet of paper and writes down a sequence $A$ with $N$ elements, where every positive integer from $1$ to $N$ appears exactly once. Then, he takes another sheet of paper and writes down $M$ statements about $A$.

Each statement has one of two forms:

• 1 x y v: The maximum number in the interval $[x, y]$ is $v$.

• 2 x y v: The minimum number in the interval $[x, y]$ is $v$.

After that, Slavko comes and steals Mirko's first sheet of paper. Mirko feels hopeless, and he wants you to find a sequence that satisfies these statements. It does not need to be exactly the same as the original sequence.

Input Format

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

The next $M$ lines each contain one statement.

Output Format

Output exactly one line: a length-$N$ sequence that satisfies all statements, where each of $1$ to $N$ appears exactly once, separated by spaces. If there is no solution, output $-1$.

3 2
1 1 1 1
2 2 2 2

1 2 3

4 2
1 1 1 1
2 3 4 1

-1

5 2
1 2 3 3
2 4 5 4

1 2 3 4 5

Hint

Translated by ChatGPT 5