Nežmah 氏は $0$ と $1$ で埋められた $n$ 行 $m$ 列のグリッドを見つけました。強迫性障害のため、彼はグリッド内のすべての $1$ を $0$ に変えたいと思っています。彼には気に入っている $k$ 個の順序対 $(a_i, b_i)$ があります。彼に行うことが許されている唯一の操作は以下の通りです：

• 最初の行または最初の列のいずれかにあるマス $(r, c)$ を 1 つ選ぶ。
• 彼が気に入っている数の組 $(a, b)$ を 1 つ選ぶ。
• マス $(r, c)$ を左上隅とする高さ $a$、幅 $b$ の長方形に含まれるすべてのマス内の数を反転させる。反転とは、すべての $0$ を $1$ に、すべての $1$ を $0$ に変えることを意味する。長方形はグリッド内に完全に含まれていなければならない。

Nežmah がグリッドをクリアするのを手伝ってください！

入力

1 行目にはテストケースの個数を表す単一の整数 $t$ ($1 \le t \le 300$) が含まれます。

各テストケースの 1 行目には、グリッドの大きさと組 $(a_i, b_i)$ の個数を表す $3$ 個の整数 $n$, $m$, $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$) が含まれます。

続く $n$ 行にはそれぞれ、0 または 1 からなる $m$ 個の文字が含まれ、グリッドを表します。

続く $k$ 行にはそれぞれ、2 つの整数 $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