Askalana终于打赢了复活赛，你跟她讲述了你们在落地后为了救活她有多么多么危险，多么多么辛苦的故事。Askalana非常感动，决定带你们冲出迷宫，一起找到离开的路。
然而你们刚离开就犯了难，眼前的门边还有一个谜题。你们发现窗户后面有一些悬浮在空中的胶状物质，于是你叫来了Askalana一起分析。你们发现，可能需要把什么东西注入到目标点中，才算成功。
但是Askalana发现，可以施法的窗口空间非常的短，于是她把一些辅助工作交给了你。

这是一个 行 列的二维垂直网格迷宫，我们使用 表示网格中从上往下数第 行和从左往右数第 列的单元格。每个方格要么是空方格 ，要么是障碍物方格 。特别的，迷宫的边缘外视作无法被摧毁的边界。

每一个障碍物的初始耐久均为 。方向向下的水流如果接触到障碍物，会使其下方的障碍物每秒损失 点耐久。当耐久为  时，再次造成耐久损失，则视为摧毁该障碍物。摧毁后，障碍物的位置在下一秒起可通行，即“水滴石穿”。
Askalana已经于第 秒在召唤了一个水源（使用 表示），水的任意部分在任意位置的任意时刻都有流动的能力，每秒扩散一个单位长度，规则如下：
在下方存在障碍物时，水流同时向左、右两侧流动。
在下方无障碍物时，水流只能向下流动。
水流路径交叉时，比如在扩散产生的水平水流上方存在一条向下流动的垂直水流，则多条路径均会生效（在本案例中，垂直水流也会使下方障碍物耐久损失），而不对原有的水平水流产生影响。但同一方向的水流产生的效果不会叠加。
已存在的水流不会消失。在迷宫边界外不存在障碍物等实体，水流流出边界视作消失。

如果水流抵达终点（使用 表示），则视为完成解谜。Askalana刚打赢复活赛魔力不足，她想知道她最短需要维持多久的水源，即水流最短经过多久可以抵达终点。如果水流无法抵达终点，输出 ，猫猫会用爆裂魔法掀桌子。

第一行输入三个整数  代表迷宫的行数、列数、每个障碍物的初始耐久。 
此后  行，每行输入一个长度为  的字符串，代表迷宫的布局。保证字符串仅由一个 、一个  和若干 、 组成。分别代表水源起点、终点、空方格、障碍物。

如果水流可以到达终点，输出一个正整数，代表水流抵达终点所需的最短时间。否则，直接输出 。

5 5 1
...*.
.....
..###
..###
#%###

6

5 5 1
...*.
.....
..###
..###
###%#

6

5 5 1
...*.
.....
..###
#.###
##%##

-1

10 10 1
.........*
..#....###
..........
#..#......
..........
..#...#.#.
.#....#...
...###....
..........
..%##.....

16