JAG land is a country, which is represented as an $M \times M$ grid. Its top-left cell is $(1, 1)$ and its bottom-right cell is $(M, M)$.

Suddenly, a bomber invaded JAG land and dropped bombs to the country. Its bombing pattern is always fixed and represented by an $N \times N$ grid. Each symbol in the bombing pattern is either `X`

or `.`

. The meaning of each symbol is as follows.

`X`

: Bomb`.`

: Empty

Here, suppose that a bomber is in $(br, bc)$ in the land and drops a bomb. The cell $(br + i - 1, bc + j - 1)$ will be damaged if the symbol in the $i$-th row and the $j$-th column of the bombing pattern is `X`

($1 \le i, j \le N$).

Initially, the bomber reached $(1, 1)$ in JAG land. The bomber repeated to move to either of $4$-directions and then dropped a bomb just $L$ times. During this attack, the values of the coordinates of the bomber were between $1$ and $M - N + 1$, inclusive, while it dropped bombs. Finally, the bomber left the country.

The moving pattern of the bomber is described as $L$ characters. The $i$-th character corresponds to the $i$-th move and the meaning of each character is as follows.

`U`

: Up`D`

: Down`L`

: Left`R`

: Right

Your task is to write a program to analyze the damage situation in JAG land. To investigate damage overview in the land, calculate the number of cells which were damaged by the bomber at least $K$ times.

The input consists of a single test case in the format below.

$N$ $M$ $K$ $L$ $B_{1}$ $\vdots$ $B_{N}$ $S$

The first line contains four integers $N$, $M$, $K$ and $L$($1 \le N < M \le 500$, $1 \le K \le L \le 2 \times 10^{5}$).
The following $N$ lines represent the bombing pattern.
$B_i$ is a string of length $N$. Each character of $B_i$ is either `X`

or `.`

. The last line denotes the moving pattern.
$S$ is a string of length $L$, which consists of either `U`

, `D`

, `L`

or `R`

.
It's guaranteed that the values of the coordinates of the bomber are between $1$ and $M - N + 1$, inclusive, while it drops bombs in the country.

Print the number of cells which were damaged by the bomber at least $K$ times.

Input | Output |
---|---|

2 3 2 4 XX X. RDLU | 3 |

7 8 3 5 .XXX.X. X..X.X. ...XX.X XX.XXXX ..XXXX. X.X.... ..XXXXX DRULD | 26 |