폭격

JAG land는 $M \times M$ 격자로 나타내는 나라이다. 왼쪽 위 칸이 $(1,1)$이고 오른쪽 아래 칸이 $(M,M)$이다.

갑자기 폭격기가 JAG land에 침입해 폭탄을 투하했다. 폭격 패턴은 항상 고정되어 있고 $N \times N$ 격자로 나타낸다. 폭격 패턴의 각 기호는 'X'(폭탄) 또는 '.'(빈 칸)이다.

폭격기가 나라의 $(b_r,b_c)$에 있고 폭탄을 투하한다고 하자. 폭격 패턴의 $i$번째 행과 $j$번째 열의 기호가 'X'이면 칸 $(b_r+i-1,b_c+j-1)$이 피해를 입는다 ($1 \le i,j \le N$).

처음에 폭격기는 JAG land의 $(1,1)$에 도착했다. 폭격기는 4방향 중 하나로 이동한 다음 폭탄을 투하하는 것을 정확히 $L$번 반복했다. 이 공격 동안 폭탄을 투하할 때 폭격기의 좌표 값은 1 이상 $M-N+1$ 이하였다. 마지막으로 폭격기는 나라를 떠났다.

폭격기의 이동 패턴은 $L$개의 문자로 주어진다. $i$번째 문자는 $i$번째 이동에 대응하고 각 문자의 의미는 다음과 같다.

'U'는 위, 'D'는 아래, 'L'은 왼쪽, 'R'은 오른쪽이다.

당신의 임무는 JAG land의 피해 상황을 분석하는 프로그램을 작성하는 것이다. 나라의 피해 개요를 조사하기 위해, 폭격기에게 $K$번 이상 피해를 입은 칸의 수를 계산하라.

입력의 첫 줄에는 네 정수 $N$, $M$, $K$, $L$이 주어진다 ($1 \le N \le M \le 500$, $1 \le K \le L \le 2 \cdot 10^5$). 다음 $N$개 줄은 폭격 패턴을 나타낸다. $B_i$는 길이 $N$의 문자열이다. $B_i$의 각 문자는 'X' 또는 '.'이다. 마지막 줄은 이동 패턴을 나타낸다. $S$는 'U', 'D', 'L', 'R'로 이루어진 길이 $L$의 문자열이다. 폭탄을 투하할 때 폭격기의 좌표 값은 1 이상 $M-N+1$ 이하임이 보장된다.

폭격기에게 $K$번 이상 피해를 입은 칸의 수를 출력한다.