## Xor Game

XORin and XORina celebrate 10 years from a very important moment for them. So they decided to play a silly game called "XOR Game". XORina writes on a paper a list of n numbers: a_{1}, a

_{2}, ..., a

_{n}. XORin has to guess it. XORina gives m clues about the sequence. A clue says that the xor sum of the elements from

*x*to

*y*equals

*val*. XORin wants a sequence following all clues, hoping that it will be XORina's sequence as well.

## Input

First line of input contains 2 values, n and m (1 ≤ n, m ≤ 100000). Next m lines contain 3 numbers: x, y, value, describing a clue (x ≤ y, 0 ≤ value ≤ 2^{20}).

## Output

Write a sequence of n numbers a_{1}, a

_{2}, ..., a

_{n}(0 ≤ a

_{i}≤ 2

^{20}) which respects all m clues. It is guaranteed that there'll always be at least one sequence following all clues.

## Sample

Input | Output |
---|---|

2 2 1 1 1 1 2 3 | 1 2 |

4 2 1 3 0 3 4 7 | 1 2 3 4 |