Treasure Hunt

Time limit1sMemory limit256 MB

Summary

Starting at (1, 1), follow the letters of S through adjacent grid tiles, and report the maximum number of full repetitions K and the final tile, or -1 if none exists.

Level: Medium4 of 10
Topics: Graph, DFS, Simulation
Solved: No attempts yet

Problem

Geonggus found a treasure map with $N$ rows and $M$ columns. On the back of the map is a string of $L$ uppercase letters and a note: "If you follow the written string $K$ times, the treasure is buried on the tile with the last character of the string."

Geonggus lives by the saying "effort never betrays," so he believes the treasure is buried where the value of $K$ is maximal. Follow the given string and find the place where Geonggus thinks the treasure is buried. Geonggus starts at $(1, 1)$ , and he can move only to the adjacent tiles above, below, left, or right.

Input

The first line contains $N$ , $M$ , and $L$ , the length of the string $S$ , separated by spaces. The top-left coordinate is $(1, 1)$ , and the bottom-right coordinate is $(N, M)$ .

The second line contains the string $S$ . $S$ consists of uppercase letters, and no letter appears more than once in $S$ .

The next $N$ lines give the map. Each line consists of uppercase letters. The tile where Geonggus stands has the same letter as the first character of $S$ .

Output

If Geonggus believes a treasure location exists, print the number of times $K$ he follows the string, followed by the coordinates of the treasure.

If Geonggus decides there is no treasure, or the treasure can never be found, print only $-1$ .

Print the maximum value of $K$ and the treasure location that corresponds to it. There are never two or more places where $K$ is maximal.

Constraints

$1 \le N, M \le 100$

$1 \le L \le 26$

Examples2

Example 1
Input
```
4 4 3
ABC
ABCA
FGEB
CBBC
CABA
```
Expected output
```
2
3 4
```
Example 2
Input
```
2 2 4
ABCD
AB
DC
```
Expected output
```
-1
```