Problems
Farmer John is training to become forklift certified! As part of his training, he needs to clear N boxes, conveniently labeled 1 through N, from an old warehouse.
The boxes can be modeled as axis-aligned rectangles in a 2-dimensional plane, where the +x-direction is east and the +y-direction is north. Box i has its southwest corner at (x_i1, y_i1) and its northeast corner at (x_i2, y_i2). All coordinates are integers in the range [1, 2N], and no two corners from different rectangles share the same x or y coordinate. All boxes have non-zero area, and no two boxes intersect.
Farmer John plans to remove the boxes one at a time out of the southwest entrance of the warehouse. However, he can only remove a box if no part of any other box lies both south and west of that box's northeast corner due to the physical limitations of the forklift.
Your task is to help Farmer John decide the order in which to remove all the boxes. Your program should work in three modes, determined by the integer flag M:
Mode 1 (M = 1): Generate a permutation of 1, ..., N that specifies a valid box removal order. If there are multiple valid orders, any one is acceptable. It can be proven that such an order always exists.
Mode 2 (M = 2): For each k = 1, ..., N, output a binary string of N characters where the k-th character is 1 if Farmer John can remove box k after boxes 1 through k-1 have been removed, and 0 otherwise.
Input
Each input consists of T (1 ≤ T ≤ 10) independent test cases. It is guaranteed that the sum of all N over all test cases does not exceed 5·10^5.
The first line of input contains T and M. (M is the same for every test case.) Each test case is formatted as follows:
The first line contains an integer N.
Each of the next N lines contains four space-separated integers: x_i1, y_i1, x_i2, y_i2, representing the southwest and northeast corners of box i.
Output
For each test case:
If M = 1, output a single line with N space-separated integers, where the j-th integer is the label of the j-th box to remove.
If M = 2, output a single line with a binary string of
N characters specifying the answer for eachk = 1, \dots, N .
Example #1
2 1
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4
1 3 2 4
2 3 1
The first test case corresponds to the
Example #2
2 2
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4
1011
011
For the first test case, box
You must sign in to write code.