Mr. Nežmah 发现了一个 $n$ 行 $m$ 列的网格，网格中填满了 0 和 1。由于强迫症，他想把网格中所有的 1 都变成 0。他有 $k$ 个他喜欢的数对 $(a_i, b_i)$。他唯一被允许进行的操作如下：

• 选择第一行或第一列中的一个单元格 $(r, c)$。
• 选择一个他喜欢的数对 $(a, b)$。
• 将以单元格 $(r, c)$ 为左上角、高为 $a$ 且宽为 $b$ 的矩形区域内的所有数字进行翻转。翻转意味着将所有的 0 变成 1，将所有的 1 变成 0。该矩形必须完全包含在网格内。

请帮助 Nežmah 清空网格！

输入格式

第一行包含一个整数 $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。

输出格式

对于每个测试用例，输出操作次数 $op$ ($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)，表示你选择翻转以 $(x_i, y_i)$ 为左上角、行数为 $a_{r_i}$ 且列数为 $b_{r_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