狂奔的Wzf

题目背景

众所周知,Wzf一直想写作业。可是今天,它的作业被WSD抢了!!!Wzf很愤怒?!他决定以最快的速度,冲向作业。在他面前是一个迷宫,作业就在其中!

题目描述

Wzf从(1,1)开始,每秒可以向上下左右某一方向走2的次方步,问至少多久可以到达作业?

输入输出格式

输入格式


第一行,两个整数,n,m。 接下来n行,每行m个字符,`$`或者`.`代表可走的空地,`X`表示障碍,`#`表示作业,(保证只有一个作业)

输出格式


Wzf到达作业最短耗时。如果没有解输出 `-1`。

输入输出样例

输入样例 #1

2 2
$$
.#

输出样例 #1

2

说明

1<n,m<1000,保证起点不是障碍