问题 E: Red and Blue and Green

Ran loves intervals, inversions and trees, so she wants to make a problem mixing all of them together!

Ran has a unknown permutation p of length n and m pairwise distinic intervals, the i-th one is [li,ri][l_i,r_i][li,ri]. It's guaranteed that for two intervals $i$ and $j$, let li≤ljl_i\le l_jli≤lj (if li=ljl_i=l_jli=lj, let ri>rjr_i> r_jri>rj), then ri<ljr_i<l_jri<lj or ri≥rjr_i\ge r_jri≥rj always holds.

There will be $m$ restrictions, the $i$-th one is like the number of inversions in [li,ri][l_i,r_i][li,ri] must be odd/even. An inversion in an array $a$ is a pair of indices (i,j)(i, j)(i,j) such that $i>j$ and ai<aja_i < a_jai<aj.

Now Ran want you to construct a permutation $p$ and meet all restrictions, or report it is impossible.

The first line contains two integers $n$ and $m$ (1≤n,m≤1031\le n,m\le 10^31≤n,m≤103).
For the next $m$ lines, each line contains three integers li,ri,wil_i,r_i,w_ili,ri,wi (1≤li≤ri≤n1\le l_i\le r_i\le n1≤li≤ri≤n, wi∈{0,1}w_i\in\{0,1\}wi∈{0,1}). If wi=0w_i=0wi=0 then the number of inversions in [li,ri][l_i,r_i][li,ri] must be even, wi=1w_i=1wi=1 otherwise.

Output $-1$ if it's impossible to construct $p$, or output $n$ integers representing $p$.

4 2
1 3 1
1 2 0

1 3 2 4