Taco Path

You are given a grid represented as a matrix of characters. Each cell of the grid is either O (open) or X (blocked). Determine whether there exists a path from the top-left corner to the bottom-right corner by moving only in four directions (up, down, left, right), and only through cells containing O.

Details:

• The grid has n rows. Each of the following n lines contains a string of equal length consisting solely of the characters O and X.
• The path must start at the cell (0, 0) (top-left) and end at (n-1, m-1) (bottom-right), where m is the number of columns.
• If the starting cell or the ending cell contains X, then the answer is False immediately.

In mathematical terms, if we label the grid cells by indices \( (i,j) \) with \( 0 \le i \lt n \) and \( 0 \le j \lt m \), then find if there exists a sequence of indices \( (i_0,j_0), (i_1,j_1), \dots, (i_k,j_k) \) such that:

[ \begin{aligned} &i_0 = 0,\quad j_0 = 0,\ &i_k = n-1,\quad j_k = m-1,\ &|i_{l+1}-i_l| + |j_{l+1}-j_l| = 1 \quad (\text{for } 0 \le l < k),\ &\text{and } grid[i_l][j_l] = 'O' \quad (0 \le l \le k). \end{aligned} ]

Your task is to print True if such a path exists and False otherwise.

inputFormat

The input is given via standard input (stdin) and has the following format:

n
row1
row2
...
row_n

Here, n (an integer) is the number of rows. Each of the next n lines contains a non-empty string representing a row of the grid. All rows have equal length. If n is 0, the grid is empty.

outputFormat

Output a single line to standard output (stdout): True if there is a valid path from the top-left to the bottom-right of the grid, and False otherwise.

## sample

4
OXOO
OOXO
XOXO
OOOO

True