Ông Nežmah tìm thấy một lưới gồm $n$ hàng và $m$ cột được điền đầy các số $0$ và $1$. Do chứng rối loạn ám ảnh cưỡng chế (OCD), ông muốn biến tất cả các số $1$ trong lưới thành số $0$. Ông có $k$ cặp số có thứ tự $(a_i, b_i)$ mà ông yêu thích. Thao tác duy nhất mà ông được phép thực hiện là:

• Chọn một ô $(r, c)$ nằm ở hàng đầu tiên hoặc cột đầu tiên.
• Chọn một cặp số $(a, b)$ mà ông yêu thích.
• Lật tất cả các số bên trong các ô nằm trong hình chữ nhật có chiều cao $a$ và chiều rộng $b$ nhận ô $(r, c)$ làm góc trên bên trái. Lật có nghĩa là đổi tất cả các số $0$ thành $1$, và các số $1$ thành $0$. Hình chữ nhật phải nằm hoàn toàn bên trong lưới.

Hãy giúp Nežmah xóa sạch lưới!

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 300$) — số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa $3$ số nguyên $n$, $m$, và $k$ ($2 \le n, m \le 1000, 1 \le k \le 20$), lần lượt là kích thước của lưới và số lượng cặp $(a_i, b_i)$.

$n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự chỉ gồm 0 hoặc 1, mô tả lưới.

$k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i < n, 1 \le b_i < m$, tất cả các cặp $(a_i, b_i)$ đều phân biệt).

Đảm bảo rằng tổng của $n$ và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $1000$.

Kết quả

Đối với mỗi bộ dữ liệu, in ra số lượng thao tác ($0 \le op \le k(n + m)$).

Trong $op$ dòng tiếp theo, mỗi dòng in ra $3$ số nguyên $r_i$, $x_i$, và $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$, ít nhất một trong hai số $x_i$ và $y_i$ bằng $1$), có nghĩa là bạn chọn lật tất cả các ô bên trong hình chữ nhật gồm $a_{r_i}$ hàng và $b_{r_i}$ cột có góc trên bên trái tại $(x_i, y_i)$.

Đảm bảo luôn tồn tại lời giải, và nếu có nhiều lời giải thì bạn có thể in ra bất kỳ lời giải nào.

Ví dụ

Dữ liệu vào 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

Kết quả 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