output

standard output

One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:

By the pieces lay a large square wooden board. The board is divided into n2

cells arranged into n rows and n

columns. Some of the cells are already occupied by single tiles stuck to it. The remaining cells are free.

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it's possible to fully tile the board?

Input

The first line of the input contains a single integer n

(3≤n≤50

) — the size of the board.

The following n

lines describe the board. The i-th line (1≤i≤n) contains a single string of length n. Its j-th character (1≤j≤n) is equal to "." if the cell in the i-th row and the j

-th column is free; it is equal to "#" if it's occupied.

You can assume that the board contains at least one free cell.

Output

Output YES if the board can be tiled by Alice's pieces, or NO otherwise. You can print each letter in any case (upper or lower).

Examples

Input

Copy

3
#.#
...
#.#

Output

Copy

YES

Input

Copy

4
##.#
#...
####
##.#

Output

Copy

NO

Input

Copy

5
#.###
....#
#....
###.#
#####

Output

Copy

YES

Input

Copy

5
#.###
....#
#....
....#
#..##

Output

Copy

NO

Note

The following sketches show the example boards and their tilings if such tilings exist:

题意：

一天，爱丽丝正在打扫她的地下室，这时她注意到一件非常奇怪的事情:一个木制的无限集合！每块由五块方形瓷砖制成，四块瓷砖靠近第五块中间瓷砖:

 

在这些碎片旁边放着一块大的方形木板。该板被分成n^2

 

排列成n行和n

 

列。一些细胞已经被粘在上面的单块瓷砖占据了。剩余的细胞是自由的。

 

爱丽丝开始怀疑她是否能完全用她找到的棋子填满棋盘。当然，每块必须正好覆盖电路板的五个不同单元，没有两块可以重叠，每块都应该完全适合电路板，没有一些部分位于电路板边界之外。然而，这块木板太大了，爱丽丝无法用手做瓷砖。你能帮助确定是否有可能完全平铺木板吗？

直接dfs每个点

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
#include<string>
char map_t[55][55];
int n,flag=0;
int jc()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(map_t[i][j]=='.')
                return 0;
        }
    }
    return 1;
}
void dfs(int i,int j)
{
    if(flag==1)
        return;
    if(i==n+1&&j==1)
    {
        if(jc()==1)
            flag=1;
        return;
    }
    if(map_t[i][j]=='#')
    {
        if(map_t[i][j+1]=='\0')
        {
            dfs(i+1,1);
        }
        else
            dfs(i,j+1);
    }
    else
    {
        if(map_t[i+1][j]=='.'&&map_t[i-1][j]=='.'&&map_t[i][j+1]=='.'&&map_t[i][j-1]=='.')
        {
            map_t[i+1][j]='#';map_t[i-1][j]='#';map_t[i][j+1]='#';map_t[i][j-1]='#';map_t[i][j]='#';
            dfs(i,j+1);
            map_t[i+1][j]='.';map_t[i-1][j]='.';map_t[i][j+1]='.';map_t[i][j-1]='.';map_t[i][j]='.';
        }
        else
        {
            if(map_t[i][j+1]=='\0')
            {
                dfs(i+1,1);
            }
            else
                dfs(i,j+1);
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        flag=0;
        memset(map_t,0,sizeof(map_t));
        for(int i=1;i<=n;i++)
        {
            scanf("%s",map_t[i]+1);
        }
        /*for(int i=0;i<=n+1;i++)
        {
            for(int j=0;j<=n+1;j++)
            {
                if(map_t[i][j]=='\0')
                {
                    printf("*");
                    continue;
                }
                printf("%c",map_t[i][j]);
            }
            printf("\n");
        }*/
        dfs(1,1);
        if(flag==1) printf("YES\n");
        else printf("NO\n");
    }
}