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 . It's guaranteed that for two intervals and , let  (if , let ), then or always holds.

There will be restrictions, the -th one is like the number of inversions in must be odd/even. An inversion in an array is a pair of indices such that and .

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

The first line contains two integers  and  ().
For the next  lines, each line contains three integers  (, ). If  then the number of inversions in  must be even,  otherwise.

Output  if it's impossible to construct , or output  integers representing .

4 2
1 3 1
1 2 0

1 3 2 4

4 1
1 1 1

-1