Searching in Binary

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem types

You are becoming a king! But wait, before you become a king, you must prove yourself worthy! Traditionally, to become a king, you must complete the following task:

You are given 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 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 following lines, the i^\text{th} line containing the range 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).

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

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


There are no comments at the moment.