9041: Red and Blue and Green

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:Special Judge 上传者:
提交:4 通过:3

题目描述

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 iii and jjj, let li≤ljl_i\le l_jlilj (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_jrirj always holds.

There will be mmm restrictions, the iii-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 aaa is a pair of indices (i,j)(i, j)(i,j) such that i>ji > ji>j and ai<aja_i < a_jai<aj.

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

输入格式

The first line contains two integers nnn and mmm (1≤n,m≤1031\le n,m\le 10^31n,m103).
For the next mmm 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 n1lirin, 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-11 if it's impossible to construct ppp, or output nnn integers representing ppp.

输入样例 复制

4 2
1 3 1
1 2 0

输出样例 复制

1 3 2 4