CF241F.Race

The Old City is a rectangular city represented as an m × n grid of blocks. This city contains many buildings, straight two-way streets and junctions. Each junction and each building is exactly one block. All the streets have width of one block and are either vertical or horizontal. There is a junction on both sides of each street. We call two blocks adjacent if and only if they share a common side. No two blocks of different streets are adjacent and no two junctions are adjacent.

There is an annual festival and as a part of it, The Old Peykan follows a special path in the city. This path starts from a block in a street, continues with many junctions and ends in a block of some street. For each street block, we know how much time it takes for the Old Peykan to go from this block to an adjacent block. Also the Old Peykan can go from each junction to its adjacent street blocks in one minute. Of course Old Peykan can't go to building blocks.

We know the initial position of the Old Peykan and the sequence of junctions that it passes to reach its destination. After passing all the junctions and reaching the destination, it will stay there forever. Your task is to find out where will the Old Peykan be k minutes after it starts moving. Consider that The Old Peykan always follows the shortest path that passes through the given sequence of junctions and reaches the destination.

Note that the Old Peykan may visit some blocks more than once.

老城区是一个矩形城市，以 $m \times n$ 的方格块形式表示。该城市包含许多建筑、笔直的双向街道以及路口。每个路口和每栋建筑恰好占据一个方格块。所有街道的宽度均为一个方格块，且仅沿水平或垂直方向延伸。每条街道的两端均各有一个路口。当且仅当两个方格块拥有公共边时，称它们为相邻。不同街道的任意两个方格块互不相邻，任意两个路口也互不相邻。

每年都会举行一场节日庆典，作为庆典的一部分，“古老佩坎”（The Old Peykan）将在城市中沿一条特殊路径行进。该路径起始于某条街道上的一个方格块，途经若干个路口，最终终止于某条街道上的一个方格块。对于每条街道上的每个方格块，我们已知“古老佩坎”从该方格块移动到其任一相邻方格块所需的时间。此外，“古老佩坎”可以从每个路口出发，在一分钟内到达其所有相邻的街道方格块。当然，“古老佩坎”无法进入建筑所占的方格块。

我们已知“古老佩坎”的初始位置，以及它为抵达目的地而必须依次经过的路口序列。在遍历完全部指定路口并抵达目的地后，“古老佩坎”将永远停留在该处。你的任务是：求出“古老佩坎”出发 $k$ 分钟后所处的位置。注意，“古老佩坎”始终沿着满足以下条件的最短路径行进：该路径必须严格按给定顺序经过全部指定路口，并最终抵达目的地。

注意：“古老佩坎”可能多次访问同一方格块。

The first line of input contains three integers m, n and k (3 ≤ m, n ≤ 100, 1 ≤ k ≤ 100000). Next m lines are representing the city's map. Each of them containts n characters, each character is a block:

• Character "#" represents a building.
• Digits "1", "2", ..., "9" represent a block of an street and this digit means the number of minutes it takes for the Old Peykan to pass this block.
• Characters "a", "b", ..., "z" means that this block is a junction and this character is it's name. All the junction names are unique.

Consider that all blocks have the coordinates: the j-th in the i-th line have coordinates (i, j) (1 ≤ i ≤ m, 1 ≤ j ≤ n).

The (m + 2)th line contains two integers r__s and c__s (1 ≤ r__s ≤ m, 1 ≤ c__s ≤ n), string s and another two integers r__e and c__e (1 ≤ r__e ≤ m, 1 ≤ c__e ≤ n). The path starts from block (r__s, c__s), continues through junctions in the order that is specified by s and will end in block (r__e, c__e). Length of s is between 1 and 1000.

It's guaranteed that string s denotes a correct path from the start position to the end position and string s doesn't contain two consecutive equal letters. Also start position (r__s, c__s) and the end position (r__e, c__e) are street blocks.

输入的第一行包含三个整数 $m$、$n$ 和 $k$（满足 $3 \le m,\,n \le 100$，$1 \le k \le 100000$）。接下来的 $m$ 行表示城市的地图。每行包含 $n$ 个字符，每个字符代表一个方块：

• 字符 # 表示一座建筑物；
• 数字 '1'、'2'、…、'9' 表示一条街道上的方块，该数字表示“老佩坎”通过该方块所需的时间（单位：分钟）；
• 字符 'a'、'b'、…、'z' 表示一个路口，该字符即为该路口的名称；所有路口名称互不相同。

规定所有方块均有坐标：第 $i$ 行第 $j$ 列的方块坐标为 $(i,\,j)$（其中 $1 \le i \le m$，$1 \le j \le n$）。

第 $(m+2)$ 行包含两个整数 $r_s$ 和 $c_s$（满足 $1 \le r_s \le m$，$1 \le c_s \le n$）、一个字符串 $s$，以及另外两个整数 $r_e$ 和 $c_e$（满足 $1 \le r_e \le m$，$1 \le c_e \le n$）。路径从方块 $(r_s,\,c_s)$ 出发，依次经过字符串 $s$ 所指定顺序的各个路口，并最终到达方块 $(r_e,\,c_e)$。字符串 $s$ 的长度在 $1$ 到 $1000$ 之间。

保证字符串 $s$ 表示一条从起点到终点的有效路径，且 $s$ 中不包含两个连续相同的字母。此外，起点 $(r_s,\,c_s)$ 和终点 $(r_e,\,c_e)$ 均为街道方块。

In a single line print two integers r__f and c__f — (r__f, c__f) being the position of the Old Peykan after exactly k minutes.

在一行中输出两个整数 $r_f$ 和 $c_f$ —— 其中 $(r_f,\,c_f)$ 表示老佩坎经过恰好 $k$ 分钟后的位置。