Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Race

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

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.

Output

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.

Examples

Input

3 10 12

##########

#z1a1111b#

##########

2 3 ab 2 8

Output

2 8

Input

10 3 5

###

#w#

#1#

#a#

#1#

#1#

#1#

#1#

#b#

###

3 2 abababababababab 6 2

Output

8 2

Input

3 10 6

##########

#z1a1311b#

##########

2 3 ab 2 8

Output

2 7

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 02:50:54 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|