Bombing

Problem Statement

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.

---

Input

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.

Output

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

Examples

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

Example

Input

Output

inputFormat

Input

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.

outputFormat

Output

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

Examples

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

Example

Input

Output

样例