Rubik's Cube#7128

Rubik's Cube

1 second

32 megabytes

Hard

Sashko, after mastering the Rubik's Cube and striving for new achievements, has invented his own puzzle. However, he does not yet know how to solve it. Here is how Sashko describes his puzzle.

You are given a square table with $2 n$ cells in each row and $2 n$ cells in each column. Each cell is filled with a natural number not exceeding $100$ . In one move, you may mirror ("flip") any row or column of the table. Below are some examples of such operations: the initial table is on the left, and on the right there are three examples showing the table after a single move. The row or column that was mirrored is highlighted.

The problem is to determine whether it is possible, using these operations, to transform the table in such a way that all four $n \times n$ n \times n corner sub-squares contain identical numbers. The numbers in different corner squares may differ from each other. If this is possible, you must specify a sequence of moves that achieves the desired configuration. For example, the following table:

can be transformed into the target form in $4$ moves (the affected rows and columns are highlighted):

Determine whether the table with the given initial configuration can be transformed as required. If possible, give the corresponding sequence of moves after which the table acquires the required form.

Input

The first line contains the integer $t$ — the number of test cases. Each test case is described in a separate block in the same format. There are no empty lines between blocks.

The first line of each block contains the positive integer $n$ .

The next $2 n$ lines of the block each contain $2 n$ natural numbers, describing the initial filling of the table. Constraints: $1 \leq t \leq 10$ 1 \leq t \leq 10, $1 \leq n \leq 100$ 1 \leq n \leq 100, every cell of the table contains a natural number not exceeding $100$ .

Output

The output should consist of $t$ blocks, in the same order as input. Each block corresponds to one test case. There should be no empty lines between blocks.

In the first line of each block, output $k$ — the number of moves needed to achieve the goal.

In the next $k$ lines, output the moves in order. For each move, print the number of the row or column that is mirrored. Numbering starts from $1$ . Columns are numbered from left to right, rows from top to bottom. Prefix the row number with a "+" sign (without quotes), and the column number with a "–" sign.

If it is impossible to achieve the desired configuration, output a single line containing "–1" in that block.

Examples

Example 1