Triangle Areas (Large)

Tangor is ten years old and has just learned how to compute the area of a triangle. He also worked out on his own that if all three vertices of a triangle have integer coordinates, the area is always an integer or half of an integer.

Today he is going the other way. Instead of measuring a triangle he already has, he picks an integer $A$ and tries to draw a triangle whose area is exactly $A/2$. The vertices may sit only on the grid points of his graph paper.

The paper is divided into an $N$ by $M$ grid of square cells, and the only points he may use as vertices are the corners of those cells. Placing a coordinate system on the paper, a usable point is $(x, y)$ for integers $x$ and $y$ with $0 \le x \le N$ and $0 \le y \le M$.

Given $N$, $M$ and $A$, find three grid points that form a triangle of area exactly $A/2$, or report that no such triangle fits on the paper.

The first line holds an integer $C$, the number of test cases.

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

Constraints

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

Print one line for each test case.

Many different triangles can have the same area, so the answer is fixed to a single canonical triangle. Let $k$ be the case number, counted from 1.

If $A > N \times M$, no triangle of area $A/2$ fits on the paper. In that case print

Case #k: IMPOSSIBLE

Otherwise let $h = \lceil A / N \rceil$ and $w = N h - A$. These satisfy $1 \le h \le M$ and $0 \le w < N$, and the triangle with vertices $(0, 0)$, $(N, 1)$ and $(w, h)$ has area exactly $A/2$. Print those vertices in that order:

Case #k: 0 0 N 1 w h

That is, print the six integers $0$, $0$, $N$, $1$, $w$, $h$ separated by single spaces.