Golden Field#258
Sign in

Golden Field

1 second
256 megabytes
Hard

Vus the Cossack accidentally found a rectangular field n \times m square meters. The field has rows and columns. Rows are numbered from to from top to bottom. Columns are numbered from to from left to right.

Cossack noticed that in some squares there are gold coins, namely: in the square, which is in the -th row and the -th column, there are exactly a_{ij} gold coins.

Just pick up all the coins — it's too easy for Vus, so he decided to take all the coins from the squares where the number of coins is even.

However, this task turned out to be too easy for him, so Vus the Cossack decided to move the coins the next way: he can take all coins in a square and transfer them to any neighboring square. Squares are considered adjacent if they have a common side. He can perform the described shift operation any number of times.

Now Cossack is wondering how many coins he can take. Help him find that number, and help him understand how he needs to move coins to pick up that number.

Note that Cossack does not need to minimize the number of shift operations, he only needs to maximize the number of coins he will take.

Input

The first line contains two integers and (1 \leq t \leq 10, 0 \leq g \leq 6) — number of tests and block number.

The first line of each test contains two integers and (1 \leq n, m \leq 50) — field sizes.

Each of the next line contains integers a_{i1}, a_{i2}, \dots, a_{im} (0 \leq a_{ij} \leq 100) — the number of gold coins in the squares.

It is not guaranteed that there is at least one coin in the field.

Output

For each test, do the following:

In the first line, print one integer — the maximum number of coins that Vus will take.

In the second line, print one integer (0 \leq p \leq 10\,000) — the number of move operations that need to be performed. Note that you do not need to minimize the value of .

In each of the following lines, print four integers x_1, y_1, x_2, y_2 (1 \leq x_1, x_2 \leq n, 1 \leq y_1, y_2 \leq m), which means that coins that are squared (x_1, y_1) must be shifted to the square (x_2, y_2).

If there are several correct answers, it is allowed to deduce any of them. It is guaranteed that there is an optimal answer, where the number of shift operations does not exceed .

Examples

Example

Loading
Loading

Note

In the first example, the Cossack can first move all the coins from the square to , after which the field will look like this:

4 0 1
9 7 0

After shifting coins from to the field will look like this:

4  0 1
16 0 0

Therefore, the answer is 4+16=20.

In the second example, the Cossack can first move all the coins from the square to , after which the field will look like this:

0 5 5  4

After shifting coins from to the field will look like this:

0 0 10 4

Therefore, the answer is 10+4=14.

Scoring

  1. ( points) n=1, all a_{ij} are even;

  2. ( points) n=1, all a_{ij} are odd;

  3. ( points) n=1;

  4. ( points) n,m>1, all a_{ij} are even;

  5. ( points) n,m>1, all a_{ij} are odd;

  6. ( points) n,m>1.