Maze Keychain Beads

In this problem, you are given a labyrinth keychain game that consists of a maze panel with several small beads. The maze is represented by an $N \times M$ grid. Some cells are obstacles (denoted by #), some cells are empty (.), and some cells contain a bead (O).

Every move, you can rotate the entire maze 90° either to the left or to the right. When you rotate the maze, the positions of both obstacles and beads are transformed. The rotations follow these formulas (using 1-indexed coordinates):

• A 90° left rotation transforms a cell at $(i,j)$ to ( (M-j+1, i) ). In 0-indexed terms, this is: ( (i,j) \to (M-1-j, i) ).
• A 90° right rotation transforms a cell at $(i,j)$ to ( (j, N-i+1) ). In 0-indexed terms, this is: ( (i,j) \to (j, N-1-i) ).

Immediately after each rotation, gravity takes effect in the new maze: every bead will "fall" downward (i.e. increasing row index) until one of the two events occurs:

1. It falls out of the maze (if there is no obstacle below).
2. It is stopped by an obstacle (denoted by #) or by another bead that has not yet fallen.

More precisely, consider a bead that lands at position $(i,j)$ after the rotation. If there exists an obstacle in the same column below it, let the smallest such row index be ( i^* ). Then, if there are exactly ( k ) beads in the cells ( (i,j), (i+1,j), \ldots, (i^-1,j) ), that bead will settle at ( (i^-k, j) ). Otherwise, if there is no obstacle below, the bead falls out of the maze.

Your task is to compute the minimum number of 90° rotations (each rotation can be either left or right) required so that all beads have fallen out of the maze.

It is guaranteed that the maze configuration is small enough to allow a breadth-first search (BFS) through the possible states. If the initial configuration has no beads, then the answer is 0. (You may assume that a solution exists.)

inputFormat

The first line contains two integers $N$ and $M$, representing the number of rows and columns of the maze.

Then follow $N$ lines, each containing a string of length $M$. Each character is one of the following:

• . representing an empty cell,
• # representing an obstacle,
• O representing a cell containing a bead.

It is guaranteed that the input is valid.

outputFormat

Output a single integer --- the minimum number of rotations (each a 90° left or right rotation) needed so that all beads fall out of the maze. If there are no beads initially, output 0.

sample

3 3
...
.O.
...

1