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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
typedef double db;
const int M=1100,O=2e5+10;
const db PI=acos(-1.0);
int dx[128],dy[128],cnt,x,y,K,n,m,len,N,r[M],l;
char s[O];
struct cp{
    db r,i;
    cp(db a=0,db b=0):r(a),i(b){}
}a[M][M],b[M][M],c[M];
inline cp operator +(cp a,cp b){return cp(a.r+b.r,a.i+b.i);}
inline cp operator -(cp a,cp b){return cp(a.r-b.r,a.i-b.i);}
inline cp operator *(cp a,cp b){return cp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}
inline cp operator /(cp a,db b){return cp(a.r/b,a.i/b);}
void DFT(cp *a,int k){
    rep(i,0,N-1){
        r[i]=(i&1)?r[i^1]|(1<<l-1):r[i>>1]>>1;
        if(i<r[i]) swap(a[i],a[r[i]]);
    }
    for(int mid=1;mid<N;mid<<=1){
        cp wn(cos(PI/mid),k*sin(PI/mid));
        for(int R=mid<<1,j=0;j<N;j+=R){
            cp w(1,0),*l=a+j,*r=a+j+mid,x,y;
            for(int k=0;k<mid;++k,++l,++r,w=w*wn)
                x=*l,y=(*r)*w,*l=x+y,*r=x-y;
        }
    }
    if(k==-1) rep(i,0,N-1) a[i]=a[i]/N;
}
void DFT_2(cp a[M][M],int k){
    rep(i,0,N-1) DFT(a[i],k);
    //rep(i,0,N-1){rep(j,0,N-1) printf("%.8lf %.8lf ",a[i][j].r,a[i][j].i);puts("");}
    rep(i,0,N-1){
        rep(j,0,N-1) c[j]=a[j][i];DFT(c,k);
        rep(j,0,N-1) a[j][i]=c[j];
    }
}
void conv(){
    for(N=1,l=0;N<m;N<<=1,l++);
    DFT_2(b,1);
    DFT_2(a,1);
    //rep(i,0,N-1){rep(j,0,N-1) printf("%.8lf %.8lf ",a[i][j].r,a[i][j].i);puts("");}
    
    //rep(i,0,N-1){rep(j,0,N-1) printf("%.8lf %.8lf ",b[i][j].r,b[i][j].i);puts("");}
    rep(i,0,N-1) rep(j,0,N-1) a[i][j]=a[i][j]*b[i][j];
    //rep(i,0,N-1){rep(j,0,N-1) printf("%.8lf %.8lf ",a[i][j].r,a[i][j].i);puts("");}
    DFT_2(a,-1);
}
int main(){
    scanf("%d%d%d%d",&n,&m,&K,&len);
    rep(i,0,n-1){
        scanf("%s",s);
        rep(j,0,n-1) b[i][j].r=s[j]=='X';
    }
    scanf("%s",s+1);
    dx['U']=-1;dx['D']=1;dy['R']=1;dy['L']=-1;
    rep(i,1,len){
        x+=dx[s[i]];y+=dy[s[i]];
        a[x][y].r++;
    }
    conv();
    //rep(i,0,m-1){rep(j,0,m-1) printf("%d ",(int)a[i][j].r);puts("");}
    rep(i,0,m-1) rep(j,0,m-1) if(a[i][j].r+0.5>=K) ++cnt;
    printf("%d\n",cnt);
    return 0;
}