M. Nežmah a trouvé une grille de $n$ lignes et $m$ colonnes remplie de $0$ et de $1$. En raison de ses TOC, il veut transformer tous les $1$ de la grille en $0$. Il possède $k$ couples de nombres $(a_i, b_i)$ qu'il aime bien. La seule opération qu'il est autorisé à effectuer est la suivante :

• Choisir une case $(r, c)$ située soit dans la première ligne, soit dans la première colonne.
• Choisir un couple de nombres $(a, b)$ qu'il aime bien.
• Inverser tous les nombres situés dans les cases contenues dans le rectangle de hauteur $a$ et de largeur $b$ dont le coin supérieur gauche est la case $(r, c)$. Inverser signifie transformer tous les $0$ en $1$ et tous les $1$ en $0$. Le rectangle doit être entièrement contenu dans la grille.

Aidez Nežmah à vider la grille !

Entrée

La première ligne contient un seul entier $t$ ($1 \le t \le 300$) — le nombre de cas de test.

La première ligne de chaque cas de test contient $3$ entiers $n$, $m$ et $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$), les dimensions de la grille et le nombre de couples $(a_i, b_i)$.

Les $n$ lignes suivantes contiennent chacune $m$ caractères, tous égaux à 0 ou 1, décrivant la grille.

Les $k$ lignes suivantes contiennent chacune deux entiers $a_i$ et $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, tous les couples $(a_i, b_i)$ sont distincts).

Il est garanti que la somme de $n$ et la somme de $m$ sur tous les cas de test ne dépassent pas $1000$.

Sortie

Pour chaque cas de test, affichez le nombre d'opérations ($0 \le op \le k(n + m)$).

Dans les $op$ lignes suivantes, affichez $3$ entiers $r_i$, $x_i$ et $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$, au moins l'un de $x_i$ et $y_i$ est égal à $1$), ce qui signifie que vous choisissez d'inverser toutes les cases à l'intérieur du rectangle de $a_{r_i}$ lignes et $b_{r_i}$ colonnes dont le coin supérieur gauche est en $(x_i, y_i)$.

L'existence d'une solution est garantie, et s'il existe plusieurs solutions, vous pouvez afficher n'importe laquelle d'entre elles.

Exemple

Entrée 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

Sortie 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