Description

There is a maze with $n$ rows and $m$ columns:

Wzf starts from the top-left corner of the maze (row $1$, column $1$). Each second, it can:

1. Choose a direction (up / down / left / right).
2. Choose a non-negative integer $m$.
3. Take one step in the chosen direction, moving $2^m$ cells:
   • It must not cross any obstacle along the way.
   • The landing cell must not contain an obstacle.
   • It cannot go outside the maze.

Find the minimum number of seconds Wzf needs to reach the goal.

Input Format

The first line contains two integers $n, m$ with $1 \le n, m \le 1000$.

The next $n$ lines each contain $m$ characters.

It is guaranteed that there is exactly one #.

It is guaranteed that the cell at row $\bm 1$, column $\bm 1$ is not X.

Output Format

Output a single integer, the minimum number of seconds Wzf needs to reach the goal.

If Wzf cannot reach the goal, output $-1$.

2 2
$$
.#

2

Hint

Translated by ChatGPT 5