Triangle Areas

Ten-year-old Tangor has just learned how to compute the area of a triangle. He is amazed that there are so many ways to do it, and he convinced himself that when all three vertices have integer coordinates, the area is always an integer or half of an integer.

Today he works in the opposite direction. Instead of drawing a triangle and computing its area, he fixes an integer $A$ and tries to draw a triangle of area exactly $A/2$. He places vertices only on the lattice points of his graph paper.

The sheet of graph paper is divided into an $N$ by $M$ grid of square cells. If you put a coordinate system on the paper, the points available as vertices are the points $(x, y)$ with integers $x$ and $y$ such that $0 \le x \le N$ and $0 \le y \le M$.

Given the integers $N$, $M$, and $A$, decide whether three lattice points form a triangle of area exactly $A/2$, and if they do, report those three points.

The first line contains the number of test cases $C$ in the input.

Each of the next $C$ lines contains three integers $N$, $M$, and $A$.

Limits

• $0 \le C \le 1000$
• $1 \le A \le 10^8$
• $1 \le N \le 50$
• $1 \le M \le 50$

For each test case, print one line. If no triangle satisfies the condition, print

Case #k: IMPOSSIBLE

where k is the case number, starting from 1. Otherwise print

Case #k: x1 y1 x2 y2 x3 y3

where $(x_1, y_1)$, $(x_2, y_2)$, and $(x_3, y_3)$ are three lattice points that form a triangle of area $A/2$.

Several triangles can satisfy the condition, so the output is pinned to one of them. Read the six printed numbers as the sequence $(x_1, y_1, x_2, y_2, x_3, y_3)$ and print the lexicographically smallest such sequence. A lexicographic comparison looks at the first position where two sequences differ. The three points may be written in any order, so in the smallest sequence they appear sorted by $(x, y)$.