JAG 国是一个国家，其领土表示为一个 $M \times M$ 的网格。其左上角单元格为 $(1, 1)$，右下角单元格为 $(M, M)$。

突然，一架轰炸机入侵了 JAG 国并向该国投掷炸弹。其轰炸模式是固定的，由一个 $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 国的 $(1, 1)$ 位置。轰炸机重复进行了 $L$ 次移动（每次向 4 个方向之一移动）并投下炸弹。在这次攻击过程中，轰炸机投弹时其坐标值均在 $1$ 到 $M-N+1$ 之间（包含边界）。最后，轰炸机离开了该国。

轰炸机的移动模式由 $L$ 个字符描述。第 $i$ 个字符对应第 $i$ 次移动，每个字符的含义如下： ‘U’ — 上，‘D’ — 下，‘L’ — 左，‘R’ — 右。

你的任务是编写一个程序来分析 JAG 国的受损情况。为了调查该国的受损概况，请计算被轰炸机至少损坏 $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$ 是一个长度为 $L$ 的字符串，由 ‘U’, ‘D’, ‘L’ 或 ‘R’ 组成。 保证轰炸机在境内投弹时，其坐标值均在 $1$ 到 $M-N+1$ 之间（包含边界）。

输出格式

输出被轰炸机至少损坏 $K$ 次的单元格数量。

样例

样例输入 1

2 3 2 4
XX
X.
RDLU

样例输出 1

3

样例输入 2

8 10 1 3
XXX.XX..
.XX...X.
XX.XXXXX
........
XXX.X..X
.X.XX..X
..X.X.X.
X.XX..X.
RRD

样例输出 2

63