There is a rumor that William R. Hamilton played chess in his youth. Already in this young age he was obsessed by paths (and cycles) which visit each location exactly once.
One afternoon when he was staring at his chessboard he got intrigued by the bishop. He started to wonder whether it is possible to move the bishop to all chessboard squares of a given color so that the bishop visits each square exactly once.
A generalized chessboard is a rectangular grid of r rows by c columns. The color of grid squares alternates between black and white, like on a regular chessboard. In this problem the squares have coordinates ranging from (1, 1) to (r, c), growing from top to bottom and from left to right. The square (1, 1) in the top left corner is always white.
A bishop is a chess figure which is allowed to move along any diagonal by an arbitrary positive number of squares. Formally, a bishop located at (x, y) can move to any of the squares (x + k, y + k), (x + k, y − k), (x − k, y + k) or (x − k, y − k) for any k > 0. Note that from these rules it follows that the bishop always stays on squares of the same color.
A bishop’s path is a sequence of chessboard squares such that each square (other than the first one) can be reached from the previous square by a bishop in one move. If a bishop’s path visits each square of a given color exactly once, we call it a bishop’s Hamiltonian path, or bishopian path for short. The path may start and end in any square of the given color.
You are given the chessboard dimensions and a color.
In the easy subproblem B1 find a bishopian path or report that no bishopian path exists.
In the hard subproblem B2 find a non-intersecting bishopian path or report that no non-intersecting bishopian path exists.
A non-intersecting bishopian path is defined as follows: If we draw the bishopian path as a polyline that connects the centers of visited squares, in order, the polyline must never overlap, cross, or even touch itself. (Formally, two consecutive line segments of the polyline can only share a single point, and any other two line segments must be completely disjoint.)
The first line of the input file contains an integer t ≤ 600 specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line of the form “r c f”, where r and c are dimensions of the chessboard and f is a character that is either W or B: the color of squares the bishop should visit. All test cases have r, c ≤ 125 and r ⋅ c ≥ 2 (the chessboard has at least 2 squares).
If there is no path of the desired type, output a single line with the text impossible.
Otherwise, for a path consisting of p squares output p lines each consisting of two integers ri and ci (1 ≤ ri ≤ r and 1 ≤ ci ≤ c): the coordinates of visited squares, in order.
In the example output below there is an empty line between the two test cases. But as with most IPSC problems, extra whitespace doesn’t matter.
Input:
2
2 6 B
1 3 WOutput:
2 1
1 2
2 3
1 4
2 5
1 6
impossibleIn the first example you are asked to find a path that visits all black squares of a chessboard with 2 rows and 6 columns. One possible solution (valid both for B1 and B2) is shown above. This output corresponds to the following diagram:
In the second example you are asked to find a path that visits all white squares on a chessboard with 1 row and 3 columns. There are two white squares and the bishop is unable to move between them, so no such path exists. Again, this answer is valid both for B1 and B2.
An example of a test case on which the answers for B1 and B2 differ is the test case “4 4 W”.