Пан Нежмах знайшов таблицю з $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