Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2566
Periodic Tilings

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In the middle of the XX-th century Roger Penrose impressed many mathematicians showing that there exists a set of tiles that can cover the whole plane, but only aperiodically. On the contrary, in this problem we are interested in periodic tilings, more of that, in regular tilings. Consider a connected set of unit squares. It is called a polyomino. A polyomino is said to tile the plane in a regular way, if one can cover the whole plane with non-overlapping copies of the selected polyomino in such a way that:

1.   all copies can be transformed one to another using translation only, rotations and flips are not allowed;
2.   each copy has the same surrounding polyominoes, that is, if we select some polyomino and translate the whole plane so that the top-left corner of the selected polyomino is in the coordinates center, the picture is the same for all polyominoes.

Given a polyomino, find out if it is possible to tile the plane with it in a regular way. You may find useful the following fact: if it is possible to tile the plane with some polyomino in a regular way, then in the tiling each polyomino has a common border of non-zero length with at most six other polyominoes.

Input

There are severval test cases.The first line of each test case is a positive integen n(0<n<=50).Then there're n lines of characters. The n lines describes a part of the plane that contains the given polyomino, represented by the characters '.'(dot) denoting empty spaces and '*'(asterisk) denoting squares that belong to the polyomino. each line contains at most 50 characters. The polyomino is constructed of at most 30 unit squares. The input is terminaled by EOF.

Output

There is only one line for each test case. Output "YES" if it is possible to tile the plane in a regular way with the polyomino given, or "NO" if it is impossible.

Sample Input

```4
....
.*..
.**.
.....
4
....
.*..
.**.*
..***
5
....
.***.
..*..
.***.
..*..
```

Sample Output

```YES
NO
YES
```

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4
Submit    Status