P8299 [COCI 2012/2013 #2] INFORMACIJE

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

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.

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

Translated by ChatGPT 5