Extravagant Experiment

Matija is a scientist who runs experiments with white rats. A rat is in a cage whose floor is divided into $n \times n$ squares. Each square is colored either white or red. Rows are numbered from $1$ to $n$ from top to bottom, and columns from left to right.

The rat can move from a square to an adjacent square that shares a side with it. However, the rat is afraid of red squares, so it never steps onto a red square.

After the rat has spent some time in the cage and learned where it may move, Matija covers it with a box of size $k \times k$ squares. The sides of the box are parallel to the sides of the cage. Even in the dark, the rat keeps moving only over white squares.

The rat's movements inside the box cannot be seen from outside. Only the movement of the box is visible. The box moves when the rat is next to the edge of the box and steps in the direction where the box is. Then the box moves one square in that direction.

The black circle is the rat, and the shaded area is the box.

Matija recorded the initial position of the box. For each move of the box, he wrote 'L' if the box moved left, 'R' if it moved right, 'U' if it moved up, and 'D' if it moved down.

Write a program that uses these records to find the minimum number of steps the rat could have taken.

The first line contains the natural numbers $n$ and $k$ ($2 \le k \le 10$, $k < n \le 100$).

Each of the next $n$ lines contains $n$ characters. Each character is either a lowercase 'b' or a lowercase 'c'. The letter 'b' is a white square, and 'c' is a red square.

The next line contains two natural numbers $r$ and $s$ ($1 \le r, s \le n - k + 1$), the row and column of the upper left corner of the box at the start of the experiment.

The next line contains the natural number $p$ ($1 \le p \le 1\,000\,000$), the number of moves of the box.

The last line contains a string of $p$ characters. Each character is one of the uppercase letters 'L', 'R', 'U', or 'D', and it gives the direction of a move of the box.

Print one line with the minimum possible number of steps the rat took.

In the second sample, the rat could start at square $(3, 1)$ and then take these 10 steps: up, down, down, right, right, right, up, right, up, up.

In the third sample, the rat could start at square $(4, 1)$ and then take these 18 steps: down, up, up, up, right, right, down, right, right, left, left, up, up, down, down, right, right, right.