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$。

輸出格式

對於每筆測試資料，輸出操作次數 ($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