Description

There are n boxes C₁, C₂,..., 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):

• I i j: The intersection volume of C_i and C_j is positive.
• X i j: The intersection volume is zero, and any point inside C_i has smaller x-coordinate than any point inside C_j.
  
• Y i j: The intersection volume is zero, and any point inside C_i has smaller y-coordinate than any point inside C_j.
  
• Z i j: The intersection volume is zero, and any point inside C_i has smaller z-coordinate than any point inside C_j.

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 x₁, y₁, z₁, x₂, y₂, z₂, that means the i-th box is the set of points (x, y, z) satisfying x₁ <= x <= x₂, y₁ <= y <= y₂, z₁ <= z <= z₂. The absolute values of x₁, y₁, z₁, x₂, y₂, z₂ should not exceed 1,000,000.

Sample Input  Download

Sample Output  Download

Tags

Discuss