← 返回题目列表

Codeforces · 152/D

D. 框架

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

有一天,Vasya 拿到一张 n × m 方格大小的方格纸。我们的瓦夏很喜欢几何图形,所以他在纸上画了两个矩形。矩形的边与坐标轴平行,且每个矩形的每条边的长度不少于3个正方形,边由网格线绘制。侧面也可以是纸张边缘的一部分。然后瓦夏在长方形的框架上孵化出所有的正方形。

让我们将矩形的框架定义为矩形内至少与其边框共享一侧的一组正方形。

过了一会儿,瓦夏发现了一张尺寸完全相同的纸,但无法猜测这是同一张纸还是不同的纸。所以,他让你检查一下他找到的那张纸上是否有两个画好的画框,除此之外什么也没有。

请注意,Vasya 绘制的框架可以任意相交、重叠甚至完全重合。

纸上的坐标是这样介绍的:X轴从上到下,方格数字的x坐标取值1到n,Y轴从左到右,方格数字的y坐标取值1到m。

输入

第一输入行包含两个整数 n 和 m (3 ≤ n, m ≤ 1000) — Vasya 找到的纸张尺寸。接下来的 n 行,每行由 m 个符号“.”组成。 (点)和“#”(数字符号),描述找到的纸张。符号“#”代表阴影方块,符号“.”代表阴影方块。代表一个无阴影的正方形。

输出

在第一行中打印单个单词“YES”或“NO”,表示找到的纸上是否确实画有两个框架。如果答案是肯定的,则在第二行打印4个整数:第一帧的左上角和右下角的坐标。第三行打印4个整数:第二帧的左上角和右下角的坐标。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4 5
#####
#.#.#
###.#
#####

输出 #1

YES
1 1 3 3
1 1 4 5

输入 #2

5 6
...###
...###
#####.
#...#.
#####.

输出 #2

NO

注意

在第一个示例中,图片上有两个帧。第一个是:

第二个是:

在第二个示例中,绘制的人物不是框架。注意有效帧的高度和宽度不小于3。