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 <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

ll power(ll k, ll n, int M){
  if(n == 0) return 1;
  if(n == 1) return k % M;

  ll res = power(k, n/2, M);

  res = res * res % M;

  if(n % 2)
    res = k % M * res % M;

  return res;
}

/* Number Theoretic Transform */

namespace NTT {
  void DFT(int m, int root, vector<int> &a, bool rev = false) {
    int N = a.size(), h = 0;

    for (int i = 0; 1 << i < N; i++) h++;
    for (int i = 0; i < N; i++) {
      int j = 0;
      for (int k = 0; k < h; k++)
        j |= (i >> k & 1) << (h - 1 - k);
      if (i < j) swap(a[i], a[j]);
    }

    for (int i = 1; i < N; i *= 2) {
      int base = power(root, (m - 1) / i / 2, m);
      if (rev) base = power(base, m - 2, m);
      ll w = 1;
      for (int j = 0; j < i; j++) {
        for (int k = 0; k < N; k += i*2) {
          int s = a[j+k], t = a[j+k+i] * w % m;
          a[j+k+0] = (s + t) % m;
          a[j+k+i] = (s - t + m) % m;
        }
        w = w * base % m;
      }
    }

    if (rev) {
      ll tmp = power(N, m-2, m);
      for(int &v : a) v = v * tmp % m;
    }
  }

  //(1012924417, 5), (924844033, 5)

  vector<int> conv(int _mod, int root, const vector<int> &a, const vector<int> &b) {
    int s = 1, t = a.size() + b.size() - 1;
    while(s < t) s *= 2;

    vector<int> F(s), G(s);
    for(int i = 0; i < (int)a.size(); i++) F[i] = a[i];
    for(int i = 0; i < (int)b.size(); i++) G[i] = b[i];
    DFT(_mod, root, F); DFT(_mod, root, G);

    for(int i = 0; i < s; i++) F[i] = (ll)F[i] * G[i] % _mod;
    DFT(_mod, root, F, true);

    return F;
  }
};


int N, M, K, L;
char B[500][501], S[SIZE];
int counter[500][500];

int main(){

  scanf("%d%d%d%d", &N, &M, &K, &L);

  for(int i=0; i<N; i++) {
    scanf("%s", B[i]);
  }

  scanf("%s", S);

  int x = 0, y = 0;

  for(int i=0; i<L; i++) {
    if (S[i] == 'R') x++;
    if (S[i] == 'L') x--;
    if (S[i] == 'D') y++;
    if (S[i] == 'U') y--;

    counter[y][x]++;
  }

  vector<int> a(M * M), b(M * M);

  for(int i=0; i<M; i++)
    for(int j=0; j<M; j++)
      a[i*M + j] = counter[i][j];

  for(int i=0; i<N; i++)
    for(int j=0; j<N; j++)
      b[i*M + j] = B[i][j] == 'X';

  auto res = NTT::conv(924844033, 5, a, b);

  int ans = 0;

  for(int i=0; i<M; i++)
    for(int j=0; j<M; j++)
      ans += res[i*M + j] >= K;

  printf("%d\n", ans);

  return 0;
}