Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Tiling Challenge

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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:

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 \leq n \leq 50$$$) — the size of the board.

The following $$$n$$$ lines describe the board. The $$$i$$$-th line ($$$1 \leq i \leq n$$$) contains a single string of length $$$n$$$. Its $$$j$$$-th character ($$$1 \leq j \leq 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

3 #.# ... #.#

Output

YES

Input

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

Output

NO

Input

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

Output

YES

Input

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

Output

NO

Note

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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2019 15:22:56 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|