← 返回题目列表

Codeforces · 1647/C

C. 小圆和幼稚的恶作剧

中文机器翻译题面 查看原题

小圆小时候是一个极其任性的女孩,她最喜欢的恶作剧之一就是在墙上画画。根据小圆的记忆,墙是一张有$$$n$$$行和$$$m$$$列的桌子,仅由零和一组成。第 $$$i$$$ 行和第 $$$j$$$ 列的单元格坐标($$$1 \le i \le n$$$、$$$1 \le j \le m$$$)为 $$$(i, j)$$$。

有一天,她看到一幅“魔法少女小圆”的画,决定把它画在墙上。最初,小圆的桌子是一张大小为 $$$n \times m$$$ 且填满零的桌子。然后她多次应用以下操作:

小圆选择桌子上的任意矩形子表,并将其涂成国际象棋颜色(子表的左上角始终为 $$$0$$$ 颜色)。请注意,某些单元格可能会被多次着色。在这种情况下,单元格的最终颜色等于上次重新绘制期间获得的颜色。

白色表示$$$0$$$,黑色表示$$$1$$$。例如,第一张图片中的桌子是用国际象棋颜色绘制的,而其他图片则不是。

为了更好地理解该语句,我们建议您阅读第一个测试的解释。

帮助小圆找到一些不超过 $$$n \cdot m$$$ 操作的序列,使您能够获得她想要的图片,或者确定这是不可能的。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 100$$$) - 表的大小。以下$$$n$$$行中的每一行都包含一个长度为$$$m$$$的字符串,仅由$$$1$$$和$$$0$$$组成——小圆想要获取的图片的描述。

输出

如果无法获得给定的图片,则打印$$$-1$$$。

否则,在第一行打印一个整数 $$$q$$$ ($$$0 \leq q \leq n \cdot m$$$) — 获取图片所需的操作数。请注意,您不需要最小化操作数量。

然后,对于每个操作(按执行顺序)打印一行,其中包含四个数字 - 矩形的左上角和右下角的坐标。

示例

输入 #1

4
4 5
01000
10100
01010
00110
2 3
001
010
3 3
110
101
000
1 1
0

输出 #1

4
1 1 3 3
3 3 4 4
4 3 4 4
4 2 4 3
1
1 2 2 3
-1
0

注意

第一个测试用例的描述如下。

在第三个测试用例中,无法绘制出所需的图像。

在第四个测试用例中,初始表格已经是所需的图片。