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