There is a grid consisting of $N \times M$ cells. Some cells in the grid are blocked and cannot be visited, while others are accessible. We want to color the accessible cells according to the following rules:

1. Start by choosing one cell as the current cell. The starting cell can be any accessible cell.
2. Choose one direction (up, down, left, or right) from the current cell and continue moving in that direction until you reach the boundary of the grid or the next cell is blocked. Note that you cannot stop in the middle of a movement.
3. If you moved horizontally (left or right) until stopping, all cells traversed horizontally are colored yellow. The starting cell is also colored yellow. If you moved vertically (up or down) until stopping, all cells traversed vertically are colored blue. The starting cell is also colored blue. (If you could not move even one cell because the direction was immediately blocked, the starting cell is still colored.)
4. If all accessible cells have been colored yellow at least once and blue at least once, the process is successful and terminates.
5. If not, repeat steps 2-4 starting from the cell where you stopped after the previous step 2. If it is impossible to color all accessible cells yellow at least once and blue at least once even by repeating this process infinitely, it is a failure.

Consider the following example. In a $2 \times 3$ grid where all cells are accessible, if you start at the top-left $(0, 0)$, no matter how you move, you cannot color all accessible cells blue at least once and yellow at least once. On the other hand, if you start at $(0, 1)$ and move as shown in the right figure, you can color all accessible cells blue at least once and yellow at least once.

Given the size and layout of the grid, determine if it is possible to color all accessible cells blue and yellow. You must implement the following function:

int yellowblue( int N, int M, vector<string> V ) ;

This function is called exactly once. $N$ and $M$ represent the dimensions of the grid. $V$ is a vector of strings of size $N$ representing the state of the grid. Each string has length $M$. If the $(i, j)$-th cell of the grid is accessible, the $j$-th character of $V[i]$ is '.', and if it is blocked, it is '#'. If there exists a starting position from which all accessible cells can be colored yellow at least once and blue at least once, return 1; otherwise, return 0.

Implementation Details

You must submit a single file named grid.cpp. This file must implement the following function:

int yellowblue( int N, int M, vector<string> V ) ;

This function must operate as described above. You may create other functions to use internally. The submitted code must not perform any input/output operations or access other files.

Constraints

• $1 \le N, M \le 1,000$. There is at least one accessible cell in the grid.

Subtasks

• Subtask 1 [30 points]: $N, M \le 50$.
• Subtask 2 [70 points]: No additional constraints.

Examples

Input 1

1 1
.

Output 1

1

Input 2

2 3
...
...

Output 2

1

Input 3

3 3
...
..#
.##

Output 3

1

Input 4

3 3
.##
#..
#..

Output 4

0

Figure 1. Example of movement in a 2x3 grid