# Box Relations

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

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

## Description

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.
.

## Input

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.

## Output

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.

## Sample Input

3 2
I 1 2
X 2 3
3 3
Z 1 2
Z 2 3
Z 3 1
1 0
0 0

## Sample Output

Case 1: POSSIBLE
0 0 0 2 2 2
1 1 1 3 3 3
8 8 8 9 9 9

Case 2: IMPOSSIBLE

Case 3: POSSIBLE
0 0 0 1 1 1

chenrui

## Source

2009 Asia Wuhan Regional Contest Hosted by