#P17955. Flipping Frenzy

Flipping Frenzy

Flipping Frenzy

题目描述

给定一个 nn 行 mm 列的二进制网格,以及 kk 个互不相同的有序数对 (ai,bi)(a_i,b_i)。

你可以执行以下操作:

  1. 选择第一行或第一列中的一个格子 (x,y)(x,y),即 x=1x=1 或 y=1y=1。
  2. 选择一个数对 (ar,br)(a_r,b_r)。
  3. 翻转以 (x,y)(x,y) 为左上角、高为 ara_r、宽为 brb_r 的矩形中的全部格子:0 变成 1,1 变成 0。

矩形必须完全位于网格内部。数对是有序的,不能自行交换矩形的高和宽。

请用不超过 k(n+m)k(n+m) 次操作把网格中的所有格子变成 0。保证存在解。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤3001\le t\le300。

每组测试用例的第一行包含三个整数 n,m,kn,m,k,满足 2≤n,m≤10002\le n,m\le1000,1≤k≤201\le k\le20。

接下来 nn 行,每行是一个长度为 mm 的 01 字符串,描述网格的一行。

接下来 kk 行,每行包含两个整数 ai,bia_i,b_i,满足 1≤ai<n1\le a_i<n、1≤bi<m1\le b_i<m。所有数对 (ai,bi)(a_i,b_i) 互不相同。

所有测试用例的 nn 之和不超过 10001000,mm 之和也不超过 10001000。每组输入均保证存在合法操作方案。

输出格式

每组测试用例先输出一个整数 opop,表示操作次数,0≤op≤k(n+m)0\le op\le k(n+m)。

接下来 opop 行,每行输出三个整数 ri,xi,yir_i,x_i,y_i,表示使用第 rir_i 种矩形,左上角为 (xi,yi)(x_i,y_i)。需要满足

$$1\le r_i\le k,\qquad 1\le x_i\le n-a_{r_i}+1,\qquad 1\le y_i\le m-b_{r_i}+1,$$

并且 xi,yix_i,y_i 中至少一个等于 11。所有下标均从 11 开始。

执行全部操作后,网格必须全为 0。若存在多个方案,输出任意一个即可。

样例 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

输出

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