STAKOR

문제

Mad scientist Matija is experimenting with lab rats. He put one lab rat into a cage, the bottom of which is a grid of N×N square cells. Each square is coloured white or red. The rows are numbered 1 through N from top to bottom; columns are numbered left to right. 

The rat can move in the four basic directions (left, right, up and down), but is afraid of red, so it will never step into a red cell. 

After having spent some time in the cage and learned where it can move, Matija covered the rat in a box of size K×K, with sides of the box parallel to the sides of the cage. Even though it is now walking in the dark, thanks to its astounding memory, the rat still only enters white cells. 

While the rat moves under the box, it is not possible to see it. From outside you can only see when the box moves, which happens when the rat pushes against an edge of the box. When that happens, the box moves in the direction in which the rat pushes. 

[이미지 1]

The solution to the example. The black circle is the rat, while the grey rectangle represents the box. 

Matija made note of the initial position of the box and the directions in which it moved. Write a program that calculates the smallest number of times the rat might have moved to cause the box to move like it did. 

입력

The first line contains two integers N and K (2 ≤ K ≤ 10, K < N ≤ 100) – the dimensions of the cage and of the box. 

Each of the following N lines contains a string of N characters, each of them either 'w' or 'r', the colour of one cell. 

The next line contains two integers R and C (1 ≤ R, C ≤ N−K+1), the row and column of the upper-left corner of the box in its initial position. 

The next line contains an integer M (1 ≤ M ≤ 1 000 000), the number of times the box moves. 

The next line contains a string of P letters, the directions in which the box moved. Each letter is one of 'L', 'R', 'U' and 'D'. 

출력

Output the smallest possible number of times the rat might have moved. 

힌트

In the second example, the rat could have initially been in cell (3, 1) and then moved up, down, down, right, right, right, up, right, up, up.

In the third example, the rat could have initially been in cell (4, 1) and then moved down, up, up, up, right, right, down, right, right, left, left, up, up, down, down, right, right, right.