Rubik's Cube
Sasha, having mastered the Rubik's Cube, has now created his own puzzle. However, he hasn't figured out how to solve it yet. Here's how Sasha describes his puzzle:
You have a square table with 2n cells in each row and 2n cells in each column, filled with natural numbers not exceeding 100. In one move, you can mirror (or "flip") any row or column of the table. Below are examples of such operations: the initial table is on the left, and on the right are three examples of the table's configuration after one possible move. The row or column that was mirrored is highlighted.
The challenge is to determine if it's possible, using these operations, to transform the table so that each of the four corner squares of size n by n contains identical numbers. The numbers in different corner squares can be different from each other. If it's possible, you need to specify the sequence of operations that achieves this result. For instance, the following table:
can be transformed into the desired form in 4 steps (the rows and columns involved in each step are highlighted):
Your task is to determine if the table can be transformed as required. If it can, provide the sequence of moves that results in the desired configuration.
Input
The first line of the input file contains the number t — the number of test cases. Following this are t blocks, each describing a test case. There are no empty lines between the blocks.
The first line of each block contains the natural number n.
The next 2n lines of the block each contain 2n natural numbers, representing the initial configuration of the table. The constraints are 1 ≤ t ≤ 10, 1 ≤ n ≤ 100, and each number in the table is a natural number not exceeding 100.
Output
The output file should contain t blocks corresponding to the t test cases in the input file. The order of the blocks must match the input: the first block in the output corresponds to the first block in the input, the second to the second, and so on. There should be no empty lines between the blocks.
In the first line of each block, write the number k — the number of operations needed to achieve the desired configuration.
In the next k lines of the block, describe each operation in the order they are performed: specify the number of the row or column that was mirrored. Numbering starts from one, with columns counted from left to right and rows from top to bottom. If a row is mirrored, prefix its number with a "+" sign; if a column is mirrored, prefix it with a "–" sign.
If it's impossible to transform the table to the desired configuration, the block should contain a single line with the number "–1".