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:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <complex>
#include <numeric>
#include <string.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const ll MOD1 = 1000000007;
const ll MOD2 = 1000000021;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

struct FFT{ // just call multiply
    typedef pair<double, double> com;
    int n;
    vector<com> a, b;
    vector<com> f[2];
    void init(vector<int>& p, vector<int>& q, int x){
        n = 1;
        while(n < x) n *= 2;
        a.resize(n, com(0,0));
        b.resize(n, com(0,0));
        rep(i,2) f[i].resize(n, com(0,0));
        rep(i,p.size()) a[i] = com(p[i],0);
        rep(i,q.size()) b[i] = com(q[i],0);
    }

    inline com com_add (com a, com b) {
        return com(a.first+b.first, a.second+b.second);
    }

    inline com com_mul (com a, com b) {
        return com(a.first*b.first-a.second*b.second, a.first*b.second+a.second*b.first);
    }
    
    vector<com> dft(vector<com>& v, bool rev){
        int x = n, u = 0;
        f[0] = v;
        int ho = 0, ge = 1;
        for(int i = 2; i <= n; i <<= 1){
            u++; x >>= 1;
            com zeta;
            if(!rev) zeta = com(cos(2*PI/i),sin(2*PI/i));
            else zeta = com(cos(2*PI/i),-sin(2*PI/i));
            com pz;
            rep(j,x){
                pz = com(1,0);
                rep(k,i){
                    if(k>=i/2) f[ge][j*i+k] = com_add(f[ho][j*(i/2)+k-i/2],com_mul(pz,f[ho][j*(i/2)+n/2+k-i/2]));
                    else f[ge][j*i+k] = com_add(f[ho][j*(i/2)+k],com_mul(pz,f[ho][j*(i/2)+n/2+k]));
                    pz = com_mul(pz, zeta);
                }
            }
            swap(ho,ge);
        }
        return f[ho];
    }
    
    vector<com> multiply(vector<int>& p, vector<int>& q){ // x: max degree
        a.clear(); b.clear(); f[0].clear(); f[1].clear();
        int x = p.size() + q.size()+1;
        init(p,q,x);
        a = dft(a,0);
        b = dft(b,0);
        rep(i,n) a[i] = com_mul(a[i],b[i]);
        a = dft(a,1);
        rep(i,n) a[i] = com(a[i].first/n, a[i].second/n);
        return a;
    }
} fft;

int N, M, K, L;
vector<string> inp;
vector<int> pat;
string s;
vector<int> cnt;

int main() {
    cin >> N >> M >> K >> L;
    inp.assign(N, "");
    rep(i,N) cin >> inp[i];
    pat.assign(M*M,0);
    rep(i,N) rep(j,N) {
        if (inp[i][j] == 'X') pat[i*M+j] = 1;
    }
    cin >> s;
    pi pos = pi(0,0);
    cnt.assign(M*M, 0);
    rep(i,s.size()) {
        if (s[i] == 'R') pos.second++;
        if (s[i] == 'L') pos.second--;
        if (s[i] == 'U') pos.first--;
        if (s[i] == 'D') pos.first++;
        cnt[pos.first*M+pos.second]++;
    }
    vector<pair<double, double>> f = fft.multiply(pat, cnt);
    int ans = 0;
    rep(i,M) {
        rep(j,M) {
            if (round(f[i*M+j].first) >= K) ans++;
        }
    }
    cout << ans << endl;
}