Remote Control Car Racing

The national remote control car racing competition is held on a grid of size \(N \times M\). The car must travel from the start (top‐left cell) to the finish (bottom‐right cell) in the shortest possible time. The grid contains obstacles which cannot be crossed (denoted by '#' in the grid); all other cells (denoted by '.') are accessible. Although every cell can be reached if there were no obstacles, the placement of obstacles might force the car to take a detour.

The twist is that even though all cars have nearly the same performance, the competitors differ in their reaction time. A competitor’s reaction time is defined as the minimum interval (in seconds) between two successive changes in the car’s direction. (Note that the initial direction chosen at the start is counted as a change of direction.) When the car is moving, it advances one cell per second in its current direction. However, after a turn the car must continue in the new direction for at least \(R\) seconds before making another turn, where \(R\) is the competitor’s reaction time. For example, two competitors with reaction times 2 and 1 seconds might have different available paths, and their minimum travel times to the finish might be different.

Your task is: In a course that is completable (i.e. there exists at least one valid path from start to finish obeying the turning constraint), for every possible reaction time (nonnegative integer) for which a valid path exists, determine the shortest travel time (in seconds) to reach the finish when the competitor’s reaction time is \(R\). If no valid path exists for a particular reaction time, do not output any result for that \(R\).

Note: The start cell is at the top‐left corner and the finish is at the bottom‐right corner of the grid. The grid indices are 0-based.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns of the grid).
Each of the following \(N\) lines contains a string of length \(M\) consisting of the characters '.' and '#', representing the free cells and obstacles respectively.

You may assume that the start cell (top‐left) and finish cell (bottom‐right) are always free (i.e. '.').

outputFormat

For each nonnegative integer reaction time \(R\) for which there exists a valid path from the start to the finish, output a line containing two integers: \(R\) and the minimum travel time (in seconds) to reach the finish under that reaction time constraint. The output should be in ascending order of \(R\). If for a given \(R\) no valid path exists, do not output a line for that \(R\>.

sample

3 3
...
.#.
...

0 4
1 4
2 4