Gambler Bo

Gambler Bo is very proficient in a matrix game.

You have a $N\times M$ matrix, every cell has a value in $\{0,1,2\}$.

In this game, you can choose a cell in the matrix, plus 2 to this cell, and plus 1 to all the adjacent cells.

for example, you choose the cell $(x,y)$, the value of $(x,y)$ will be plused 2, and the value of $(x-1,y)(x+1,y)(x,y-1)(x,y+1)$ will be plused 1.

if you choose the cell $(1,2)$, the cell $(1,2)$ will be plused 2, and the cell $(2,2)(1,1)(1,3)$ will be plused 1, the cell $(0,2)$ won't be changed because it's out of the matrix.

If the values of some cells is exceed 2, then these values will be modulo 3.

Gambler Bo gives you such a matrix, your task is making all value of this matrix to 0 by doing above operations no more than $2NM$ times.

First line, an integer $T$. There are $T$ test cases.

In each test, first line is two integers $N,M$, and following $N$ lines describe the matrix of this test case.

$T\leq 10,1\leq N,M\leq 30$, the matrix is random and guarantee that there is at least one operation solution.

For each test, first line contains an integer $num(0\leq num\leq 2NM)$ describing the operation times.

Following $num$ lines, each line contains two integers $x,y(1\leq x\leq N,1\leq y\leq M)$ describing the operation cell.

The answer may not be unique, you can output any one.

2
2 3
2 1 2
0 2 0
3 3
1 0 1
0 1 0
1 0 1

1
1 2
5
1 1
1 3
2 2
3 1
3 3

绍兴一中

2016 Multi-University Training Contest 3