红牛喜欢解谜。
有一天,红牛发现了两块一模一样的拼图,旁边有“做一个矩形”的说明。这些碎片可以用 n × m 的字符网格来描述,其中字符“X”表示拼图的一部分,“.”表示拼图的一部分。表示网格的空白部分。保证拼图块是一个 4 连通块。有关如何指定拼图的确切详细信息,请参阅输入格式和示例。
拼图块非常重,因此红牛无法旋转或翻转拼图块。然而,他可以将它们向任何方向移动。拼图块也不能重叠。
您将获得其中一件作品的描述作为输入。确定是否可以从给定输入的两个相同副本创建一个矩形。矩形应该是实心的,即其内部或边界上不应有空洞。请记住,红牛不允许翻转或旋转棋子,并且棋子不能重叠,即来自不同棋子的两个“X”不能共享相同的位置。
输入
输入的第一行将包含两个整数 n 和 m (1 ≤ n, m ≤ 500),即拼图的尺寸。
接下来的 n 行将描述拼图。每行的长度为 m 并且由字符“.”组成和仅“X”。 “X”对应于拼图的一部分“.”是一个空的空间。
保证输入中至少有一个“X”字符,并且“X”字符形成一个 4 连通区域。
输出
如果红牛可以制作矩形,则输出“YES”。否则输出“NO”。
示例
输入 #1
2 3 XXX XXX
输出 #1
YES
输入 #2
2 2 .X XX
输出 #2
NO
输入 #3
5 5 ..... ..X.. ..... ..... .....
输出 #3
YES
注意
对于第一个示例,我们可以形成的矩形的一个示例如下
对于第二个样本,如果不旋转或翻转,就不可能将其中的两个块放置成一个矩形。
在第三个示例中,我们可以将第一个图块向右移动一位,然后组成以下矩形: