Description
elfness被魔王抓走了，这次魔王把elfness关在一个n*m的地牢里。地牢的某个地方安装了一个带锁的门，钥匙藏在地牢的另外一个地方，elfness想要通过这个门，就必须先走到藏钥匙的地方取钥匙。刚开始的时候elfness被关在(sx,sy)的位置，而离开地牢的门在(ex,ey)的位置。elfness每分钟只能从一个位置走到相邻四个位置中的其中一个。魔王每t分钟都回地牢视察一次，若发现elfness不在原位置便会把他拎回去。经过若干次的尝试，elfness已经画出了整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候还未到出口都算逃亡失败。
Input
第一行有三个整数n,m,t。接下来的n行m列为地牢的地图，其中包括:
. 代表路
* 代表墙
@ 代表elfness的起始位置
^ 代表地牢的出口
A 代表带锁的门
a 代表钥匙
Output
输出为一行，包含一个整数。对于可以成功逃亡的情况，请输出至少需要多少分钟才能离开，如果不能则输出-1。
Sample Input
4 4 100
@..A
a.*.
***.
^...
Sample Output
11
HINT
【数据范围】
对于100%的数据，2<=n,m<=20，t>0