Pan Nežmah znalazł siatkę o $n$ wierszach i $m$ kolumnach wypełnioną zerami ($0$) i jedynkami ($1$). Z powodu swojego OCD chce zamienić wszystkie jedynki w siatce na zera. Ma $k$ uporządkowanych par liczb $(a_i, b_i)$, które lubi. Jedyna operacja, jaką może wykonać, jest następująca:

• Wybierz komórkę $(r, c)$ znajdującą się w pierwszym wierszu lub w pierwszej kolumnie.
• Wybierz jedną parę liczb $(a, b)$, którą lubi.
• Odwróć wszystkie liczby w komórkach zawartych w prostokącie o wysokości $a$ i szerokości $b$, którego lewym górnym rogiem jest komórka $(r, c)$. Odwrócenie oznacza zamianę wszystkich $0$ na $1$, a wszystkich $1$ na $0$. Prostokąt musi w całości mieścić się w siatce.

Pomóż Nežmahowi wyczyścić siatkę!

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 300$) — liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera $3$ liczby całkowite $n$, $m$ oraz $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$), oznaczające wymiary siatki oraz liczbę par $(a_i, b_i)$.

Kolejne $n$ wierszy zawiera po $m$ znaków, z których każdy to 0 lub 1, opisujących siatkę.

Kolejne $k$ wierszy zawiera po dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, wszystkie pary $(a_i, b_i)$ są parami różne).

Gwarantuje się, że suma $n$ oraz suma $m$ po wszystkich przypadkach testowych nie przekracza $1000$.

Wyjście

Dla każdego przypadku testowego wypisz liczbę operacji ($0 \le op \le k(n + m)$).

W kolejnych $op$ wierszach wypisz po $3$ liczby całkowite $r_i$, $x_i$ oraz $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$, co najmniej jedna z liczb $x_i$ oraz $y_i$ jest równa $1$), co oznacza, że decydujesz się odwrócić wszystkie komórki wewnątrz prostokąta o $a_{r_i}$ wierszach i $b_{r_i}$ kolumnach, którego lewy górny róg znajduje się w $(x_i, y_i)$.

Gwarantuje się, że rozwiązanie istnieje, a jeśli istnieje wiele rozwiązań, możesz wypisać dowolne z nich.

Przykład

Wejście 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

Wyjście 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