This is problem 3 of the Victor's Various Adventures problem set.

Victor is becoming a king! But wait, before he becomes a king, he must prove himself worthy! Traditionally, to become a king, one must complete the following task:

You are given a line of ~N~ marbles, each marble is either black or white. You are then given ~M~ requirements, where the ~i^\text{th}~ requirement states that between marbles ~L_i~ and ~R_i~ there must be exactly ~a_i~ white marbles. You must find one such valid arrangement! It is guaranteed that there will always be a valid arrangement!

Can you help Victor solve this task?

Input Specification

The first line consists of the integer ~T~ ~(1 \le T \le 100)~ indicating the number of test cases.

Each test case will start with the integers ~N~ ~(1 \le N \le 15)~ and ~M~ ~(1 \le M \le 10)~ on its own line, representing the number of marbles and requirements respectively.

There will be ~M~ lines that follows, where the the ~i^\text{th}~ line contains the integers ~L_i~, ~R_i~ ~(1 \le L_i \le R_i \le N)~ and the sum ~a_i~ ~(0 \le a_i \le R_i - L_i + 1)~, all of which describe the ~i^\text{th}~ requirement.

Output Specification

For each test case, output a valid sequence on its own line.

Please note, white marbles should be represented as the digit 1 and black marbles with the digit 0.

There could be multiple solutions, any valid solution will be accepted.

Sample Input

2
8 2
1 4 3
1 8 5
5 6
3 3 0
1 5 3
1 3 2
2 5 2
2 4 2
1 5 3

Sample Output

1 0 1 1 0 0 1 1
1 1 0 1 0