Problem Description

This problem uses a Special Judge.

Farmer John divided the farm into a matrix with $r$ rows and $c$ columns, and found that cows cannot pass through some areas. Now, Bessie is in the cell with coordinates $(1,1)$, and she wants to reach the barn at $(r,c)$ to enjoy dinner. She knows that starting from her current cell and moving each time to one of the four adjacent cells, there is always at least one path that can reach the barn.

There may be infinitely many such paths. Please output any one of them, and make sure the number of moves needed does not exceed $100000$.

Input Format

The first line contains two integers $r, c$.

The next $r$ lines each contain $c$ characters, indicating whether Bessie can pass through the corresponding cell. Each character is either . or *.

• . means Bessie can pass through this cell.
• * means Bessie cannot pass through this cell.

Output Format

Output several lines. Each line contains two integers separated by a space, representing the coordinates of the cells Bessie passes through in order.

Obviously, the first line of the output is 1 1, and the last line is r c.

The cells represented by two adjacent coordinates must be adjacent.

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8

Hint

Constraints

For $100\%$ of the testdata, $1 \le r \le 113$, $1 \le c \le 77$.

Sample Explanation

The figure shows an illustration of a sample output. The answer is not unique.

Translated by ChatGPT 5