本题有弱化版 暂不可透露。

题目背景

落霞与孤鹜齐飞，秋水共长天一色

题目描述

搭着升降机登上了阁顶的小 L，看到了滚滚的江水。此时正值落日时分，小 L 看到远飞的孤雁和远方云霄上的晚霞，不禁吟诵道：“孤雁与晚霞齐飞，江水共云霄一色。”（王勃不要跳出来揍我）

小 L 的文化素养确实不高，但是他的视力极好。极目远眺，发现在江水旁边的芦苇荡上，有一只孤雁在寻找它的同伴。注意到芦苇荡被一些礁石和江水分成了 $n$ 行 $m$ 列的网格，其中原点为 $(0,0)$。注意力惊人的小 L 将那只孤雁的坐标定为 $(0, 0)$，它的同伴的坐标定为 $(n-1, m-1)$。但是这个网格中，因为晚霞太闪了，所以有的地方不能通过，用 - 表示。平时，孤雁因为其灵活的身躯，可以往前后左右以及对角线上的四个方向移动。但是寻找同伴的孤雁很累啊，该怎么办捏？小 L 再次注意到，虽然都在芦苇荡里面，但是有的路特别好走（用 ! 表示），有的路不好走（用 + 表示）。在好走的路上，孤雁能在前后左右四个方向上移动 $2$ 次（$2$ 次的方向可以不同，比如先向上再向右），但是就算这样，如果在这两格任意一格有闪耀的晚霞，孤雁也不能通过；在难走的路上，孤雁只能往前后左右四个方向走。现在小 L 想知道，孤雁至少走几步才能找到它的同伴？（注意，当连续移动 $2$ 次时，如果第一次到达了 $(n-1, m-1)$，不算找到同伴）

输入格式

第一行输入两个整数 $n, m$，用空格隔开；

后 $n$ 行每行用空格隔开输入 $m$ 个字符，表示芦苇荡的矩阵。

输出格式

输出共一行，输出一个整数，表示最少的步数。（此处认为站到 $(0, 0)$ 上也算一步）

如果孤雁无法找到它的同伴，请输出 -1。

输入输出样例

1 1
+

1

1 1
-

-1

3 3
+++
+-+
+++

5

4 6
+++--+
+-++-+
+-++-+
+--+++

15

4 6
+-+-+-
-+-+-+
+-+-+-
-+-+-+

-1

4 6
+++-++
+-+++-
+-+--+
+--++-

11

1 1
!

1

1 10
!!!!!!!!!!

-1

1 5
!-!-!

-1

1 5
!!-!!

-1

4 6
+!!++!
++++++
++!!!+
!+++++

6

4 6
+++-++
!-+-!+
+-+-!+
!-++++

12

说明/提示

数据规模与约定

1. $1 \le n, m \le 1000$
2. 矩阵中仅含 +、-、! 三种字符