在本题中，你需要判断一个拼图是否至少存在一个有效的解。

该拼图包含一个 $N \times N$ 的网格。最初，边缘上的 $4N - 4$ 个单元格被涂成红色或绿色，其余单元格被涂成白色。每个分割两个相邻白色单元格的线段被涂成黑色或灰色。

为了解决这个拼图，你必须将每个白色单元格涂成红色或绿色，使得：

• 被灰色线段隔开的两个相邻单元格必须涂成相同的颜色。
• 最终的网格不得包含“禁止模式”。

有四种禁止模式，如下图所示：

下图展示了该拼图的一个可能的问题描述及一个有效解：

问题与解

拼图的信息给出如下。从上往下第 $i$ 行、从左往右第 $j$ 列的单元格标记为 $(i, j)$。对于每个边缘单元格，其 $s_{i,j}$ 为 'o' 或 'x'，这些字符分别代表绿色和红色。对于每个非边缘单元格 $(i, j)$，$s_{i,j}$ 是一个大写字母。如果两个相邻的非边缘单元格标记有相同的字符，则它们被灰色线段隔开。否则，它们被黑色线段隔开。

判断给定的拼图是否至少存在一个解。

输入格式

$N$ $s_{1,1} \dots s_{1,N}$ $\vdots$ $s_{N,1} \dots s_{N,N}$

• $3 \le N \le 30$
• 如果 $(i, j)$ 是 $4N - 4$ 个边缘单元格之一，$s_{i,j}$ 为 'o' 或 'x'。
• 如果 $(i, j)$ 不是边缘单元格，$s_{i,j}$ 是一个大写字母。

输出格式

如果拼图至少存在一个有效解，输出 "YES"。否则输出 "NO"。

样例

样例输入 1

5
oooxx
oBABx
oABAx
xBABo
xooox

样例输出 1

NO