eolymp
bolt
Try our new interface for solving problems
Problems

Nut's string

Nut's string

Time limit 2 seconds
Memory limit 256 MiB

Squirrel Scrat got old and gained wisdom. Instead of chasing that same nut, he now wants to build a collection of different types of nuts. There are 26 different types of nuts in total, labeled with symbols from ‘a’ to ‘z’. And the ideal collection that Scrat wants to collect is described by the string s, the i-th character of which denotes the kind of i-th nut in the collection.

The mainland that Scrat now sits on can be thought of as a rectangular field of size n * m. We number the rows of the field from 1 to n from top to bottom, and the columns of the field from 1 to m from left to right. Cell (x, y) is at the intersection of row number x and column number y. Initially, the Scrat is in the cell (s[x], s[y]). In the cell with coordinates (i, j) you can find only nuts of the form x[i,j], but in an infinitely large number. The relief of the continent is arranged in such a way that movement is possible only between adjacent cells on the side and takes exactly one time.

Scrat is very principled, so it will collect nuts exactly in the order in which they are given by the string s (in other words, if s = "ab", then you cannot first pick up a nut of the form 'b' followed by a nut of the form 'a'). Help him determine the minimum time in which he can collect the entire collection. No time is wasted trying to pick up a nut in the cell where Scrat is now.

Input data

The first line contains two integers n and m (1n, m300) - the size of the continent. The second line contains two integers s[x] and s[y] (1s[x]n, 1s[y]m) - coordinates of the cell where Scrat is initially located.

Each of the following n lines consists of exactly m lowercase English letters. In the i-th of these lines, the j-th character specifies x[i,j] - the kind of nuts growing in the mainland cell (i, j). It is guaranteed that each kind of nuts is present in at least one cell of the mainland.

The next line contains a string s (1|s|300) of lowercase English letters, giving the sequence of nuts in the ideal collection.

Output data

Print the minimum time Scrat needs to complete his collection.

Examples

Input example #1
2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut
Output example #1
17
Input example #2
7 7
4 4
abcdefg
xyzabch
wnopqdi
vmvwrej
ulutsfk
tkjihgl
srqponm
squirrel
Output example #2
17

Note

In the first example, the optimal route is to reach 'n' in the first line in 12 steps, then go down 1 and add 'u' and 't' standing in a row on the right, that will require 4 more steps.

In the second example, the optimal route is given by points (4, 4), ‘s’ (5, 5), ‘q’ (3, 5), ‘u’ (5, 3), ‘i’ (6, 4), ‘r’ (4, 5) (twice), ‘e’ (4, 6) and ‘l’ (6, 7).

Source 2021 ITMO University, Second personal olympiad, February 13, Problem B