Господин Нежмах нашёл таблицу из $n$ строк и $m$ столбцов, заполненную нулями ($0$) и единицами ($1$). Из-за своего ОКР он хочет превратить все единицы в таблице в нули. У него есть $k$ упорядоченных пар чисел $(a_i, b_i)$, которые ему нравятся. Единственная операция, которую ему разрешено делать, следующая:

• Выбрать клетку $(r, c)$, находящуюся либо в первой строке, либо в первом столбце.
• Выбрать одну пару чисел $(a, b)$, которая ему нравится.
• Инвертировать все числа в клетках, содержащихся в прямоугольнике высоты $a$ и ширины $b$, верхним левым углом которого является клетка $(r, c)$. Инвертирование означает замену всех $0$ на $1$, а всех $1$ на $0$. Прямоугольник должен полностью помещаться внутри таблицы.

Помогите Нежмаху очистить таблицу!

Входные данные

Первая строка содержит одно целое число $t$ ($1 \le t \le 300$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит $3$ целых числа $n$, $m$ и $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$) — размеры таблицы и количество пар $(a_i, b_i)$.

Следующие $n$ строк содержат по $m$ символов, каждый из которых равен 0 или 1, описывающих таблицу.

Следующие $k$ строк содержат по два целых числа $a_i$ и $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, все пары $(a_i, b_i)$ различны).

Гарантируется, что сумма $n$ и сумма $m$ по всем наборам входных данных не превосходят $1000$.

Выходные данные

Для каждого набора входных данных выведите количество операций ($0 \le op \le k(n + m)$).

В следующих $op$ строках выведите по $3$ целых числа $r_i$, $x_i$ и $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$, хотя бы одно из чисел $x_i$ и $y_i$ равно $1$), означающих, что вы выбираете инвертировать все клетки внутри прямоугольника из $a_{r_i}$ строк и $b_{r_i}$ столбцов с верхним левым углом в $(x_i, y_i)$.

Гарантируется, что решение существует, а если решений несколько, вы можете вывести любое из них.

Пример

Входные данные 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

Выходные данные 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