题目描述

卢卡斯被困在了一个二维迷宫中。

这个二维迷宫可以看成一个 $n$ 行 $m$ 列的网格。我们用 $(i, j)$ 表示迷宫中第 $i$ 行第 $j$ 列的那个格子。

格子包含以下两种类型：

• .：表示可以通行的格子；
• ?：表示传送门（传送门可以视为一种特殊的可以通行的格子）；
• #：表示不能通行的墙壁。

卢卡斯初始时在迷宫的左上角 $(1,1)$ 位置，它需要移动到迷宫的右下角 $(n,m)$ 位置，那里是迷宫的出口。

每次移动，卢卡斯可以从当前格子移动到上、下、左、右相邻的格子，但是不能移动到不可通行的墙壁，也不能移动到迷宫外。

每移动一格的代价是 $1$。

但是，如果卢卡斯目前所在的位置是一个传送门，他可以从当前所在的传送门直接传输到迷宫中任意一个其它传送门。且在传送门之间穿梭的代价为 $0$。

求：卢卡斯从迷宫的左上角移动到迷宫的右下角的最小总代价。

输入格式

第一行，两个整数 $n$ 和 $m$，以空格分隔，表示迷宫的行和列。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示这个二维迷宫。

输出格式

如果卢卡斯不存在任何可行的方案，输出一行 $-1$。

否则，输出一个整数，表示卢卡斯从迷宫的左上角移动到迷宫的右下角的最小总代价。

样例

2 3
.?#
#.?

1

6 5
.#...
.#.#.
.#.#.
.#.#.
.#.#.
?#?#.

17

5 5
..#..
..#?.
#####
..#..
?.#..

-1

说明/提示

数据规模与约定

• 对于 $10\%$ 的数据，$n,m \le 5$
• 对于 $30\%$ 的数据，$n,m \le 50$
• 对于 $100\%$ 的数据，$2 \le n,m \le 500$，起点 $(1, 1)$ 是可通行的格子。