Gambler Bo

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)


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.

Sample Input

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

Sample Output

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




2016 Multi-University Training Contest 3