Herr Nežmah hat ein Gitter mit $n$ Zeilen und $m$ Spalten gefunden, das mit $0$-en und $1$-en gefüllt ist. Wegen seines Ordnungszwangs möchte er alle Einsen im Gitter in Nullen verwandeln. Er hat $k$ geordnete Zahlenpaare $(a_i, b_i)$, die er mag. Die einzige Operation, die er ausführen darf, ist die folgende:

• Wähle eine Zelle $(r, c)$ entweder in der ersten Zeile oder in der ersten Spalte.
• Wähle ein Zahlenpaar $(a, b)$, das er mag.
• Drehe alle Zahlen in den Zellen um, die in dem Rechteck der Höhe $a$ und Breite $b$ liegen, dessen obere linke Ecke die Zelle $(r, c)$ ist. Umdrehen bedeutet, alle $0$-en in $1$-en und alle $1$-en in $0$-en zu ändern. Das Rechteck muss vollständig im Gitter enthalten sein.

Hilf Nežmah, das Gitter zu leeren!

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 300$) — die Anzahl der Testfälle.

Die erste Zeile jedes Testfalls enthält $3$ ganze Zahlen $n$, $m$ und $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$), die Dimensionen des Gitters und die Anzahl der Paare $(a_i, b_i)$.

Die nächsten $n$ Zeilen enthalten jeweils $m$ Zeichen, die alle 0 oder 1 sind und das Gitter beschreiben.

Die nächsten $k$ Zeilen enthalten jeweils zwei ganze Zahlen $a_i$ und $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, alle Paare $(a_i, b_i)$ sind paarweise verschieden).

Es wird garantiert, dass die Summe von $n$ und die Summe von $m$ über alle Testfälle hinweg $1000$ nicht überschreiten.

Ausgabe

Gib für jeden Testfall die Anzahl der Operationen aus ($0 \le op \le k(n + m)$).

Gib in den nächsten $op$ Zeilen jeweils $3$ ganze Zahlen $r_i$, $x_i$ und $y_i$ aus ($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$, mindestens eines von $x_i$ und $y_i$ ist gleich $1$), was bedeutet, dass du alle Zellen innerhalb des Rechtecks mit $a_{r_i}$ Zeilen und $b_{r_i}$ Spalten und der oberen linken Ecke bei $(x_i, y_i)$ umdrehst.

Es wird garantiert, dass eine Lösung existiert, und falls es mehrere Lösungen gibt, kannst du eine beliebige davon ausgeben.

Beispiel

Eingabe 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

Ausgabe 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