Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

There are *n* boxes *C*_{1}, C_{2}, ..., C_{n} 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*):

There are four kinds of relations (1 <=

- I i j: The intersection volume of
*C*and_{i}*C*is positive._{j} - X i j: The intersection volume is zero, and any point inside
*C*has smaller_{i}*x*-coordinate than any point inside*C*._{j} - Y i j: The intersection volume is zero, and any point inside
*C*has smaller_{i}*y*-coordinate than any point inside*C*._{j} - Z i j: The intersection volume is zero, and any point inside
*C*has smaller_{i}*z*-coordinate than any point inside*C*._{j}

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.

Print a blank line after the output of each test case.

提交代码