Il signor Nežmah ha trovato una griglia con $n$ righe e $m$ colonne riempita di $0$ e $1$. A causa del suo disturbo ossessivo-compulsivo, vuole trasformare tutti gli uno della griglia in zeri. Ha $k$ coppie ordinate di numeri $(a_i, b_i)$ che gli piacciono. L'unica operazione che gli è consentito fare è la seguente:

• Scegliere una cella $(r, c)$ situata nella prima riga oppure nella prima colonna.
• Scegliere una coppia di numeri $(a, b)$ che gli piace.
• Invertire tutti i numeri all'interno delle celle contenute nel rettangolo di altezza $a$ e larghezza $b$ il cui angolo superiore sinistro è la cella $(r, c)$. Invertire significa cambiare tutti gli $0$ in $1$ e tutti gli $1$ in $0$. Il rettangolo deve essere interamente contenuto nella griglia.

Aiuta Nežmah a ripulire la griglia!

Input

La prima riga contiene un singolo intero $t$ ($1 \le t \le 300$) — il numero di casi di test.

La prima riga di ogni caso di test contiene $3$ interi $n$, $m$ e $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$), le dimensioni della griglia e il numero di coppie $(a_i, b_i)$.

Le successive $n$ righe contengono ciascuna $m$ caratteri, tutti uguali a 0 o 1, che descrivono la griglia.

Le successive $k$ righe contengono ciascuna due interi $a_i$ e $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, tutte le coppie $(a_i, b_i)$ sono distinte).

È garantito che la somma di $n$ e la somma di $m$ su tutti i casi di test non superino $1000$.

Output

Per ogni caso di test, stampa il numero di operazioni ($0 \le op \le k(n + m)$).

Nelle successive $op$ righe, stampa $3$ interi $r_i$, $x_i$ e $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$, almeno uno tra $x_i$ e $y_i$ è uguale a $1$), indicando che scegli di invertire tutte le celle all'interno del rettangolo con $a_{r_i}$ righe e $b_{r_i}$ colonne il cui angolo superiore sinistro si trova in $(x_i, y_i)$.

È garantito che esista una soluzione e, se esistono più soluzioni, puoi stamparne una qualsiasi.

Esempio

Input 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

Output 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