Bunty and Chunty are playing a game where Bunty guesses Chunty's hidden array of size N.

Bunty knows that Chunty's array has only 1s and 0s. Chunty will give Q hints about his array of the following form:

l r x Indicating that the bitwise OR of all elements in the array from index l to r is equal to x.

Now, Chunty wants Bunty to guess the lexiographically largest possible array that satisfies all the Q hints.

eg: if there is 1 hint "1 2 0" and array is of size 4. The lexiographically largest array satisfying it is 0 0 1 1.

Other arrays that satisfy it that aren't lexiographically largest include : 0 0 1 0, 0 0 0 1 etc.

Input Format

First-line has $T$, number of test cases.

Second-line has $N$ and  $Q$, the length of array $A$ and the number of hints respectively.

The following $Q$ lines have 3 space-separated integers denoting $l, \ r, and \ x$.

Output Format

Print the lexiographically largest array satisfying all the $Q$ conditions on a new line seperated by spaces for each test case.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N, Q \leq 10^{5}\\ 1 \leq l, r \leq N \\ 0 \leq x \leq 1$

It is guaranteed that at least one array exists for the given hints. (No contradicting hints are present)