Scientist

A scientist has placed a lab mouse in a cage made of N×N square cells. Each cell is either white or red. Rows are numbered 1 through N from top to bottom, and columns are numbered 1 through N from left to right.

The mouse can move one cell at a time in the four cardinal directions: left, right, up, and down. Since it is afraid of red, it never enters a red cell.

The mouse is now inside a K×K box. Every side of the box is parallel to the sides of the cage grid. The inside of the box is very dark, but the mouse knows exactly which cells are red, so it still avoids red cells.

The scientist cannot see the mouse's position inside the box and can only observe the box's movement from outside. If the mouse tries to move one cell outward while standing on an edge of the box, the box moves one cell in that direction, and the mouse moves one cell with it.

In the figure, the black circle represents the mouse, and the gray rectangle represents the box.

Given the initial position of the box and the sequence of directions in which the box moved, find the minimum number of moves the mouse must make to produce exactly that sequence.

The first line contains the cage size N and the box size K. (2 ≤ K ≤ 10, K < N ≤ 100)

Each of the next N lines describes one row of the cage. A red cell is written as r, and a white cell is written as w.

The next line contains R and C, the initial position of the box. This is the coordinate of the box's upper-left corner. (1 ≤ R, C ≤ N-K+1)

The next line contains M, the number of times the box moved. (1 ≤ M ≤ 100,000)

The last line contains the movement directions of the box in order. Each character is one of L, R, U, and D.

Print the minimum number of mouse moves needed to move the box according to the given sequence.