Bombing

JAG land is a country 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 on the country. Its bombing pattern is always fixed and is represented by an $N \times N$ grid. Each symbol in the bombing pattern is either 'X' (bomb) or '.' (empty).

Suppose the bomber is at $(b_r,b_c)$ in the land and drops a bomb. The cell $(b_r+i-1,b_c+j-1)$ is 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 arrived at $(1,1)$ in JAG land. The bomber repeated moving in one of 4 directions and then dropping a bomb exactly $L$ times. During this attack, the values of the bomber's coordinates were between 1 and $M-N+1$, inclusive, whenever it dropped bombs. Finally, the bomber left the country.

The bomber's movement pattern is given as $L$ characters. The $i$-th character corresponds to the $i$-th move and the meaning of each character is as follows.

'U' is up, 'D' is down, 'L' is left, and 'R' is right.

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

The first line of the input contains four integers $N$, $M$, $K$, and $L$ ($1 \le N \le M \le 500$, $1 \le K \le L \le 2 \cdot 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 is the movement pattern. $S$ is a string of length $L$ consisting of 'U', 'D', 'L', or 'R'. It is guaranteed that the values of the bomber's coordinates are between 1 and $M-N+1$, inclusive, whenever it drops bombs in the country.

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