描述

背景：刚做完题的你肯定饿了不行 于是你为了奖励自己从HFL家里偷走了一个蛋糕，发现后的HFL: 好家伙，你完了[○･｀Д´･ ○] 于是对你穷追不舍，你必须逃脱HFL的追捕。 但HFL的家里像个迷宫，快赶紧逃出。 HFL的家里是一个迷宫由N行M列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走;有的格子是钥匙，能用来开门；有的格子是门，有钥匙才能开门。图中’*‘表示障碍物，’.‘表示空地，’#‘表示一道门，’^‘表示一把钥匙，’$‘表示你所在的位置，’&'就是HFL家的终点。结果求出最少步数。钥匙和门和终点有，但仅且一个。规定只能上下左右4个方向。

输入描述

第一行是两个整数，N和M，代表HFL家的长和宽。（ 1≤ N，M ≤ 25)

接下来是N行，每行M个字符,每个字符之间有一个空格，代表HFL家。

输出描述

共一行，逃出HFL家最少步数(不算出发那一步）。 如果不能逃出输出"no";

用例输入 1

5 5 $ . . * .

. # . * ^

. * . . .

. * * * *

. . . . &

用例输出

1 8

提示

(数据不大，有内容上的陷阱)