XOR Game

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₁, a₂, ..., 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²⁰).

Output

Write a sequence of n numbers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 2²⁰) 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