题目描述

十岁的 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$。

3
1 1 1
1 2 64
10 10 1

Case #1: 0 0 0 1 1 1
Case #2: IMPOSSIBLE
Case #3: 1 1 2 3 5 8

提示

数据范围

• $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 翻译