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<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<map>
#include<complex>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<ll, ll> P;

#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define all(x) (x).begin(),(x).end()
#define stop char nyaa; cin>>nyaa;

typedef long double ld;
typedef complex<ld>com;
typedef vector<com> poly;
const ld pi = acos(-1.0);
const ld eps = 0.01;
poly dft(poly f, bool inverse = false) {
	int n = f.size(); int i, j, k;
	for (int i = 0, j = 1; j < n - 1; j++) {
		for (k = n >> 1; k > (i ^= k); k >>= 1);
		if (i > j)swap(f[i], f[j]);
	}
	for (int m = 2; m <= n; m *= 2) {
		com zeta = com(cos(2 * pi / (ld)m), sin(2 * pi / (ld)m));
		if (inverse) {
			zeta = com(cos(2 * pi*(m - 1) / (ld)m), sin(2 * pi*(m - 1) / (ld)m));
		}
		for (i = 0; i < n; i += m) {
			com powzeta = 1;
			for (k = i; k < i + m / 2; k++) {
				com t1 = f[k], t2 = powzeta * f[k + m / 2];
				f[k] = t1 + t2; f[k + m / 2] = t1 - t2;
				powzeta *= zeta;
			}
		}
	}
	if (inverse) {
		for (i = 0; i < n; i++) {
			f[i] /= (ld)n;
		}
	}
	return f;
}
poly multiply(poly g,poly h) {
	int n = 1; int sz = g.size() + h.size();
	while (n <= sz)n *= 2;
	while (g.size() < n) {
		g.push_back(0);
	}
	while (h.size() < n) {
		h.push_back(0);
	}
	poly gg = dft(g);
	poly hh = dft(h);
	poly ff;
	rep(i, n) {
		ff.push_back(gg[i] * hh[i]);
	}
	return dft(ff, true);
}

char mp[500][500];
int num[500][500];

int sum[500][500];
ll cnt[500][500];

void solve() {
	int n, m, k, l; cin >> n >> m >> k >> l;
	rep(i, n) {
		rep(j, n) {
			cin >> mp[i][j];
		}
	}
	string s; cin >> s;
	int x = 0, y = 0;
	rep(i, l) {
		if (s[i] == 'R') {
			y++;
		}
		else if (s[i] == 'L') {
			y--;
		}
		else if (s[i] == 'U') {
			x--;
		}
		else {
			x++;
		}
		num[x][y]++;
	}
	poly a1;
	rep(i, m) {
		rep(j, m) {
			a1.push_back(num[i][j]);
		}
	}
	poly a2;
	rep(i, m) {
		rep(j, m) {
			if (i < n&&j < n) {
				if (mp[i][j] == 'X') {
					a2.push_back(1);
				}
				else {
					a2.push_back(0);
				}
			}
			else {
				a2.push_back(0);
			}
		}
	}
	poly aft = multiply(a1, a2);
	int ans = 0;
	rep(i, m*m) {
		//cout << aft[i] << endl;
		int t = (real(aft[i]) + eps);
		if (t >= k)ans++;
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//find_prime();
	solve();
	//stop
		return 0;
}