삼각형 넓이 만들기

열 살 Tangor는 삼각형의 넓이를 구하는 방법을 막 배웠다. 구하는 방법이 여러 가지나 된다는 사실에 놀랐고, 세 꼭짓점의 좌표가 모두 정수면 넓이가 항상 정수 아니면 정수의 절반이 된다는 것도 스스로 확인했다.

오늘은 반대 방향으로 문제를 만든다. 삼각형을 먼저 그려 놓고 넓이를 구하는 대신, 정수 $A$를 정해 놓고 넓이가 정확히 $A/2$인 삼각형을 그리려고 한다. 꼭짓점은 모눈종이의 격자점에만 놓는다.

모눈종이는 가로 $N$칸, 세로 $M$칸의 정사각형 칸으로 나뉘어 있다. 종이에 좌표계를 놓으면 꼭짓점으로 쓸 수 있는 점은 $0 \le x \le N$, $0 \le y \le M$인 정수 $x$, $y$로 이루어진 $(x, y)$다.

정수 $N$, $M$, $A$가 주어질 때 넓이가 정확히 $A/2$인 삼각형을 격자점 세 개로 만들 수 있는지 판정하고, 만들 수 있으면 그 세 점을 구하라.

첫 줄에 입력에 들어 있는 테스트 케이스의 개수 $C$가 주어진다.

이어지는 $C$개의 줄에는 각각 세 정수 $N$, $M$, $A$가 주어진다.

제한

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

각 테스트 케이스마다 한 줄을 출력한다. 조건을 만족하는 삼각형이 없으면

Case #k: IMPOSSIBLE

를 출력한다. 여기서 k는 1부터 시작하는 테스트 케이스 번호다. 삼각형이 있으면

Case #k: x1 y1 x2 y2 x3 y3

을 출력한다. $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$은 넓이가 $A/2$인 삼각형을 이루는 격자점 세 개다.

답이 여러 개일 수 있으므로 출력은 하나로 고정한다. 출력하는 여섯 수를 $(x_1, y_1, x_2, y_2, x_3, y_3)$ 순서의 수열로 보고, 조건을 만족하는 수열 가운데 사전순으로 가장 작은 것을 출력한다. 사전순 비교는 앞에서부터 처음으로 값이 다른 자리를 비교한다. 세 점을 적는 순서는 자유이므로, 사전순으로 가장 작은 수열에서는 세 점이 $(x, y)$의 사전순으로 정렬되어 나온다.