El Sr. Nežmah encontró una cuadrícula con $n$ filas y $m$ columnas llena de $0$ y $1$. Debido a su TOC, quiere convertir todos los unos de la cuadrícula en ceros. Tiene $k$ pares ordenados de números $(a_i, b_i)$ que le gustan. La única operación que tiene permitido hacer es la siguiente:

• Elegir una celda $(r, c)$ que esté dentro de la primera fila o de la primera columna.
• Elegir un par de números $(a, b)$ que le guste.
• Voltear todos los números dentro de las celdas contenidas en el rectángulo de altura $a$ y anchura $b$ cuya esquina superior izquierda es la celda $(r, c)$. Voltear significa cambiar todos los $0$ por $1$, y todos los $1$ por $0$. El rectángulo debe estar completamente contenido en la cuadrícula.

¡Ayuda a Nežmah a limpiar la cuadrícula!

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 300$) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene $3$ enteros $n$, $m$ y $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$), las dimensiones de la cuadrícula y el número de pares $(a_i, b_i)$.

Las siguientes $n$ líneas contienen $m$ caracteres cada una, que son todos 0 o 1, describiendo la cuadrícula.

Las siguientes $k$ líneas contienen cada una dos enteros $a_i$ y $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, todos los pares $(a_i, b_i)$ son distintos).

Se garantiza que la suma de $n$ y la suma de $m$ en todos los casos de prueba no superan $1000$.

Salida

Para cada caso de prueba, imprime el número de operaciones ($0 \le op \le k(n + m)$).

En las siguientes $op$ líneas, imprime $3$ enteros $r_i$, $x_i$ y $y_i$ ($1 \le r_i \le k, 1 \le x_i \le n - a_{r_i} + 1, 1 \le y_i \le m - b_{r_i} + 1$, al menos uno de $x_i$ y $y_i$ es igual a $1$), lo que significa que eliges voltear todas las celdas dentro del rectángulo con $a_{r_i}$ filas y $b_{r_i}$ columnas cuya esquina superior izquierda está en $(x_i, y_i)$.

Se garantiza que existe una solución, y si hay múltiples soluciones puedes imprimir cualquiera de ellas.

Ejemplo

Entrada 1

5
6 6 2
000000
111110
000000
100001
011111
111110
5 5
3 5
4 5 2
10111
00101
10000
01100
1 3
2 1
2 2 1
00
00
1 1
5 5 3
10100
10010
00000
01101
00100
3 4
2 3
4 2
5 5 4
01010
01010
10101
00100
00100
2 2
2 3
3 2
3 3

Salida 1

5
1 1 2
2 1 2
2 2 1
2 3 1
2 4 1
6
1 1 1
1 1 2
1 4 1
2 1 3
2 1 5
2 3 1
0
10
1 1 1
1 1 2
1 2 1
2 1 1
2 1 2
2 4 1
3 1 1
3 1 2
3 1 4
3 2 1
5
3 1 4
2 1 3
4 1 2
2 4 1
3 3 1