题目背景

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

题目描述

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

输入格式

第一行，两个整数，n，m。

接下来n行，每行m个字符，$或者.代表可走的空地，X表示障碍，#表示作业，（保证只有一个作业）

输出格式

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

2 2
$$
.#

2

提示

1<n,m<1000