세 개의 룩
시간 제한2초메모리 제한256 MB
n×m 체스판에 룩 세 개를 서로 다른 칸에 놓아 정확히 k개의 칸이 공격받도록 만들 수 있는지 판정하고, 가능하면 룩의 좌표를 출력한다.
문제
이전 예선 라운드 전에 만들어진 삼색 체스가 심사위원 모두에게 큰 호평을 받아, 그들은 이 인기 있는 게임을 계속 실험해 보기로 했다. 이번에는 심사위원 한 명이 각 플레이어의 룩 수를 세 개로 늘리자고 제안했다. 새 규칙이 얼마나 흥미로울지 알아보기 위해, 심사위원들은 룩을 여러 방식으로 배치했을 때 몇 개의 칸이 "공격받는" 상태가 되는지 확인하기로 했다.
어떤 칸에 룩이 없고, 그 칸과 같은 세로줄이나 가로줄에 있는 룩이 존재하면 그 칸은 공격받는 상태이다.
게임을 분석하기 위해 심사위원들은 룩 세 개를 보드에 배치해 공격받는 칸이 정확히 k개가 되도록 할 수 있는지 알고 싶어 한다. 가능하다면 그러한 배치를 찾아야 한다.
입력
첫째 줄에는 정수 T (1 ≤ T ≤ 104)가 주어진다. 이는 테스트 예제의 수이다. 다음 T개 줄 각각에는 음이 아닌 정수 n, m, k가 주어지며, n과 m은 체스판의 크기이다 (1 ≤ n, m ≤ 109, 0 ≤ k ≤ 109).
출력
각 테스트 예제마다 한 줄에 답을 출력한다. 룩을 원하는 방식으로 배치할 수 없다면 "IMPOSSIBLE"을 출력한다. 그렇지 않으면 룩 세 개의 좌표를 나타내는 세 쌍의 수를 출력한다. 첫 번째 수는 1부터 n까지, 두 번째 수는 1부터 m까지의 범위에 있어야 한다. 두 룩을 같은 칸에 놓을 수 없다.
이 문제에서는 대회 시작 후 30분 동안 WA 대신 PE가 출력될 수 있었다. 사과드린다.