Tangor, cậu bé mười tuổi, vừa khám phá ra cách tính diện tích của một hình tam giác. Là một cậu bé thông minh, cậu ngạc nhiên trước việc có rất nhiều cách khác nhau để tính diện tích. Cậu cũng tự thuyết phục bản thân rằng, nếu tất cả các đỉnh của tam giác đều có tọa độ nguyên, thì diện tích của tam giác đó luôn là một số nguyên hoặc một nửa của một số nguyên! Thật thú vị phải không?

Nhưng hôm nay Tangor đang cố gắng làm điều ngược lại. Thay vì lấy một hình tam giác và tính diện tích của nó, cậu ấy lấy một số nguyên \(A\) và cố gắng vẽ một hình tam giác có diện tích là \(A/2\). Cậu ấy tự giới hạn mình chỉ sử dụng các điểm nguyên trên giấy kẻ ô vuông để làm các đỉnh của tam giác.

Chính xác hơn, tờ giấy kẻ ô vuông được chia thành một lưới các ô vuông kích thước \(N \times M\). Các đỉnh của tam giác chỉ có thể được đặt tại các góc của các ô đó. Nếu bạn tưởng tượng một hệ tọa độ trên tờ giấy, thì các điểm này có dạng \((x, y)\), trong đó \(x\) và \(y\) là các số nguyên sao cho \(0 \le x \le N\) và \(0 \le y \le M\).

Cho số nguyên \(A\), hãy giúp Tangor tìm ba điểm nguyên trên tờ giấy kẻ ô vuông sao cho diện tích của tam giác tạo bởi các điểm đó đúng bằng \(A/2\), nếu có thể. Trong trường hợp có nhiều cách để thực hiện việc này, bất kỳ giải pháp nào cũng sẽ làm cậu ấy hài lòng.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(C\), số lượng bộ dữ liệu trong tệp đầu vào.
• \(C\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(N, M\), và \(A\) như mô tả ở trên.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng. Nếu không có cách nào thỏa mãn điều kiện, in ra:

Case #k: IMPOSSIBLE

Case #k: x1 y1 x2 y2 x3 y3

Ràng buộc

• \(0 \le C \le 1000\)
• \(1 \le A \le 10^8\)

Phân nhóm

• Small dataset (Tập kiểm tra 1 - Công khai): \(1 \le N \le 50, 1 \le M \le 50\).
• Large dataset (Tập kiểm tra 2 - Ẩn): \(1 \le N \le 10000, 1 \le M \le 10000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2008, Vòng 2, bài Triangle Areas.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.