Problem: 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

Solution (in CPP):

Solution:
//qqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzk
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <sstream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// #define MP make_pair
// #define int long long
// #define us unsigned
//#define LL long long
const int N = 1000;
const int M = 2e5;
#define re register
// const int mod = 19260817;
// const int inf = 999999999;
// char buf[(int)1e8], *ss = buf;
// inline int init()
// {
//     buf[fread(buf, 1, (int)1e8 - 1, stdin)] = '\n';
//     fclose(stdin);
//     return 0;
// }
// const int __START__ = init();

int a, b, c, d, k[M + 10], sum[N + 10][N + 10], top, ans, p[N + 10][N + 10];
char t[N + 10][N + 10], op;
struct node
{
    int x, y;
} s[N * N + 10];

signed main()
{
    scanf("%d%d%d%d\n", &a, &b, &c, &d);
    for (re int i = 1; i <= a; i++)
        scanf("%s\n", t[i] + 1);
    int x = 1, y = 1;
    for (re int i = 1; i <= d; i++)
    {
        scanf("%c", &op);
        if (op == 'R')
        {
            y++;
            p[x][y]++;
        }
        if (op == 'L')
        {
            y--;
            p[x][y]++;
        }
        if (op == 'U')
        {
            x--;
            p[x][y]++;
        }
        if (op == 'D')
        {
            x++;
            p[x][y]++;
        }
    }
    for (re int k = 1; k <= b; k++)
        for (re int l = 1; l <= b; l++)
        {
            if (!p[k][l])
                continue;
            for (re int i = 1; k + i - 1 <= b; i++)
                for (re int j = 1; l + j - 1 <= b; j++)
                {
                    if (t[i][j] == 'X')
                        sum[k + i - 1][l + j - 1] += p[k][l];
                }
        }
    for (re int i = 1; i <= b; i++)
        for (re int j = 1; j <= b; j++)
            if (sum[i][j] >= c)
                ans++;
    printf("%d\n", ans);
    return 0;
}