There are
n boxes
C1, C2, ..., Cn in 3D space. The edges of the boxes are parallel to the
x, y or
z-axis. We provide some relations of the boxes, and your task is to construct a set of boxes satisfying all these relations.
There are four kinds of relations (1 <=
i,j <=
n,
i is different from
j):
- I i j: The intersection volume of Ci and Cj is positive.
- X i j: The intersection volume is zero, and any point inside Ci has smaller x-coordinate than any point inside Cj.
- Y i j: The intersection volume is zero, and any point inside Ci has smaller y-coordinate than any point inside Cj.
- Z i j: The intersection volume is zero, and any point inside Ci has smaller z-coordinate than any point inside Cj.
.
There will be at most 30 test cases. Each case begins with a line containing two integers
n (1 <=
n <= 1,000) and
R (0 <=
R <= 100,000), the number of boxes and the number of relations. Each of the following
R lines describes a relation, written in the format above. The last test case is followed by
n=
R=0, which should not be processed.
For each test case, print the case number and either the word POSSIBLE or IMPOSSIBLE. If it's possible to construct the set of boxes, the
i-th line of the following
n lines contains six integers
x1, y1, z1, x2, y2, z2, that means the
i-th box is the set of points (
x,y,z) satisfying
x1 <= x <= x2, y1 <= y <= y2, z1 <= z <= z2. The absolute values of
x1, y1, z1, x2, y2, z2 should not exceed 1,000,000.
Print a blank line after the output of each test case.