← 返回题目列表

Codeforces · 1185/E

E. 坡旅甲和蛇

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

经过一周的辛苦工作后,波利卡普更喜欢享受乐趣。坡旅甲最喜欢的娱乐是画蛇。他拿了一张大小为 $$$n \times m$$$ 的矩形格子纸(其中 $$$n$$$ 是行数,$$$m$$$ 是列数),并开始在单元格中画蛇。

Polycarp 用小写拉丁字母绘制蛇。他总是用符号“a”画第一条蛇,用符号“b”画第二条蛇,用符号“c”画第三条蛇,依此类推。所有的蛇都有自己独特的象征。拉丁字母里只有$$$26$$$字母,坡旅甲很累,他不想发明新的符号,所以画的蛇总数不超过$$$26$$$。

由于到了周末波利卡普已经很累了,他把蛇画成没有弯曲的直线。因此,每条蛇要么垂直要么水平放置。任何蛇的宽度等于 $$$1$$$,即每条蛇的大小为 $$$1 \times l$$$ 或 $$$l \times 1$$$,其中 $$$l$$$ 是蛇的长度。请注意,蛇不能弯曲。

当坡旅甲绘制一条新蛇时,他可以使用已经占用的单元格来绘制蛇。在这种情况下,他将蛇“越过顶部”绘制并覆盖单元格中的先前值。

最近,波利卡普在工作时发现了一张带有拉丁字母的方格纸。他想知道是否可以通过按照上述规则画一些蛇,从一张空纸上得到这张纸。如果可以的话,他对画蛇的方法很感兴趣。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 要解决的测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例描述的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \le n,m \le 2000$$$)——分别是方格纸的长度和宽度。

接下来的$$$n$$$行测试用例描述包含$$$m$$$符号,它们负责工作表上相应单元格的内容。它可以是小写拉丁字母或符号点(“.”),代表空单元格。

保证一次测试中所有纸张的总面积不超过$$$4\cdot10^6$$$。

输出

打印输入中每个测试用例的答案。

在测试用例的输出的第一行中,如果可以画蛇,则打印 YES,以便您可以从输入中获取一张纸。如果不可能,请打印 NO。

如果这个问题的答案是肯定的,那么按照下面的格式打印画蛇的方法。在下一行中打印一个整数 $$$k$$$ ($$$0 \le k \le 26$$$) — 蛇的数量。然后打印 $$$k$$$ 行,每行打印四个整数 $$$r_{1,i}$$$, $$$c_{1,i}$$$, $$$r_{2,i}$$$ 和 $$$c_{2,i}$$$ - 第 $$$i$$$ 条蛇的极端单元格坐标 ($$$1 \le r_{1,i}, r_{2,i} \le n$$$, $$$1 \le c_{1,i}, c_{2,i} \le m$$$)。蛇应该按照绘制的顺序打印。如果有多个解决方案,您可以打印其中任何一个。

请注意,波利卡普开始用一张空纸画蛇。

示例

输入 #1

1
5 6
...a..
..bbb.
...a..
.cccc.
...a..

输出 #1

YES
3
1 4 5 4
2 3 2 5
4 2 4 5

输入 #2

3
3 3
...
...
...
4 4
..c.
adda
bbcb
....
3 5
..b..
aaaaa
..b..

输出 #2

YES
0
YES
4
2 1 2 4
3 1 3 4
1 3 3 3
2 2 2 3
NO

输入 #3

2
3 3
...
.a.
...
2 2
bb
cc

输出 #3

YES
1
2 2 2 2
YES
3
1 1 1 2
1 1 1 2
2 1 2 2