Three Rooks
Time limit2sMemory limit256 MB
Given n, m, and k, decide whether three non-attacking rooks on an n by m board can attack exactly k cells, and if so give their coordinates.
- Level
Medium7 of 10
- Topics
- Math, Implementation, Brute force, Combinatorics
- Solved
- No attempts yet
Problem
The three-colored chess invented before the previous qualifying round was a big hit with all the jury members, and they decided to keep experimenting with this popular game. This time one of the jury members suggested raising the number of rooks for each player to three. To understand how interesting the game would be under the new rules, the jury members decided to look at how many cells end up "attacked" under various arrangements of the rooks.
A cell is attacked if there is no rook on that cell and there exists a rook on the same column or row as that cell.
To analyze the game, the jury wants to know whether it is possible to place three rooks on the board so that exactly k cells are attacked. If it is possible, they need to find such an arrangement.
Input
The first line contains an integer T (1 ≤ T ≤ 104), the number of test cases. Each of the next T lines contains three non-negative integers n, m, and k, where n and m are the dimensions of the chessboard (1 ≤ n, m ≤ 109, 0 ≤ k ≤ 109).
Output
For each of the T test cases, print the answer on a single line. If the rooks cannot be placed in the required way, print "IMPOSSIBLE". Otherwise print three pairs of numbers, the coordinates of the rooks. The first number must be between 1 and n, and the second between 1 and m. Two rooks cannot be placed on the same cell.
In this problem, for the first 30 minutes of the contest, PE could be returned instead of WA. We apologize.