คุณ Nežmah พบตารางขนาด $n$ แถว และ $m$ คอลัมน์ ที่เต็มไปด้วยเลข $0$ และ $1$ เนื่องจากอาการย้ำคิดย้ำทำ (OCD) ของเขา เขาจึงต้องการเปลี่ยนเลข $1$ ทั้งหมดในตารางให้กลายเป็นเลข $0$ เขามีคู่อันดับของตัวเลข $(a_i, b_i)$ ที่เขาชอบอยู่ $k$ คู่ การดำเนินการเพียงอย่างเดียวที่เขาได้รับอนุญาตให้ทำคือ:

• เลือกช่อง $(r, c)$ ที่อยู่ภายในแถวแรกหรือคอลัมน์แรก
• เลือกคู่ของตัวเลข $(a, b)$ ที่เขาชอบมาหนึ่งคู่
• พลิกตัวเลขทั้งหมดภายในช่องที่อยู่ในสี่เหลี่ยมผืนผ้าที่มีความสูง $a$ และความกว้าง $b$ ซึ่งมีมุมบนซ้ายอยู่ที่ช่อง $(r, c)$ การพลิกหมายถึงการเปลี่ยนเลข $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$) ซึ่งหมายความว่าคุณเลือกที่จะพลิกทุกช่องภายในสี่เหลี่ยมผืนผ้าที่มี $a_{r_i}$ แถว และ $b_{r_i}$ คอลัมน์ โดยมีมุมบนซ้ายอยู่ที่ $(x_i, y_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