老城是一个矩形城市,由 m × n 的街区网格表示。这座城市有许多建筑物、笔直的双向街道和交叉路口。每个路口和每个建筑物都是一个街区。所有街道的宽度均为一个街区,要么是垂直的,要么是水平的。每条街道的两侧都有一个路口。当且仅当两个块共享公共边时,我们才称它们为相邻块。不同街道的两个街区不相邻,也不存在两个路口相邻。
每年都会举办一次节日,作为节日的一部分,老佩坎 (The Old Peykan) 遵循城市中的一条特殊道路。这条路径从一条街道的一个街区开始,经过许多路口,最终到达某个街道的一个街区。对于每个街区,我们知道老佩坎从这个街区到相邻街区需要多少时间。此外,Old Peykan 可以在一分钟内从每个路口到达邻近的街区。老佩坎当然不能去搭积木。
我们知道老佩坎的初始位置以及它到达目的地所经过的路口顺序。经过所有路口并到达目的地后,它将永远停留在那里。你的任务是找出老佩坎开始移动后 k 分钟的位置。考虑老佩坎始终遵循穿过给定顺序的路口并到达目的地的最短路径。
请注意,老佩坎可能会多次访问某些街区。
输入
输入的第一行包含三个整数 m、n 和 k (3 ≤ m, n ≤ 100, 1 ≤ k ≤ 100000)。接下来的 m 行代表城市的地图。每个包含n个字符,每个字符是一个块:
- 字符“#”代表建筑物。
- 数字“1”、“2”、...、“9”代表街道的一个街区,这个数字表示老佩坎通过这个街区所需的分钟数。
- 字符“a”,“b”,...,“z”表示该块是一个路口,并且该字符是它的名称。所有连接点名称都是唯一的。
考虑所有块都具有坐标:第 i 行中的第 j 个块具有坐标 (i, j) (1 ≤ i ≤ m, 1 ≤ j ≤ n)。
第 (m + 2) 行包含两个整数 rs 和 cs (1 ≤ rs ≤ m, 1 ≤ cs ≤ n)、字符串 s 和另外两个整数 re 和 ce (1 ≤ re ≤ m, 1 ≤ ce ≤ n)。该路径从块 (rs, cs) 开始,按照 s 指定的顺序继续通过交汇点,并以块 (re, ce) 结束。 s 的长度在 1 到 1000 之间。
保证字符串 s 表示从起始位置到结束位置的正确路径,并且字符串 s 不包含两个连续的相等字母。起始位置(rs,cs)和结束位置(re,ce)也是街道街区。
输出
在一行中打印两个整数 rf 和 cf — (rf, cf) 是 Old Peykan 在恰好 k 分钟后的位置。
示例
输入 #1
3 10 12 ########## #z1a1111b# ########## 2 3 ab 2 8
输出 #1
2 8
输入 #2
10 3 5 ### #w# #1# #a# #1# #1# #1# #1# #b# ### 3 2 abababababababab 6 2
输出 #2
8 2
输入 #3
3 10 6 ########## #z1a1311b# ########## 2 3 ab 2 8
输出 #3
2 7