P13467 [GCJ 2008 #2] Triangle Areas

十岁的 Tangor 刚刚学会了如何计算三角形的面积。作为一个聪明的孩子，他对计算面积的多种方法感到惊奇。他还确信，如果三角形的所有顶点坐标都是整数，那么三角形的面积总是整数或半整数！这不是很神奇吗？ 但今天 Tangor 想要反过来。他不是给定一个三角形去计算面积，而是给定一个整数 $A$，试图画出一个面积为 $A/2$ 的三角形。他只允许使用方格纸上的整数点作为三角形的顶点。 更具体地说，这张方格纸被划分为 $N$ 行 $M$ 列的正方形格子。三角形的顶点只能放在这些格子的角上。如果你在纸上建立一个坐标系，这些点的形式为 $(x, y)$，其中 $x$ 和 $y$ 是整数，满足 $0 \leq x \leq N$ 且 $0 \leq y \leq M$。 给定整数 $A$，请你帮助 Tangor 找到方格纸上的三个整数点，使得它们组成的三角形面积恰好为 $A/2$，如果可能的话。如果有多种方案，任意一种都可以让他高兴。

第一行包含一个整数 $C$，表示输入文件中的测试用例数。 接下来的 $C$ 行，每行包含三个整数 $N$、$M$ 和 $A$，如上所述。

对于每个测试用例，输出一行。如果无法满足条件，输出 Case #k: IMPOSSIBLE 其中 $k$ 是测试用例编号，从 1 开始。否则，输出 Case #k: $x_1$ $y_1$ $x_2$ $y_2$ $x_3$ $y_3$ 其中 $k$ 是测试用例编号，$(x_1, y_1)$、$(x_2, y_2)$、$(x_3, y_3)$ 是任意三个在方格纸上的整数点，且它们组成的三角形面积恰好为 $A/2$。

**数据范围** - $0 \leq C \leq 1000$ - $1 \leq A \leq 10^8$ **小数据集（5 分，测试点 1 - 可见）** - $1 \leq N \leq 50$ - $1 \leq M \leq 50$ **大数据集（15 分，测试点 2 - 隐藏）** - $1 \leq N \leq 10000$ - $1 \leq M \leq 10000$ 由 ChatGPT 4.1 翻译