{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003eProblem Statement\u003c/h3\u003e\n\u003cp\u003eJAG 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)$.\u003c/p\u003e\n\u003cp\u003eSuddenly, 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 \u003ccode\u003eX\u003c/code\u003e or \u003ccode\u003e.\u003c/code\u003e. The meaning of each symbol is as follows.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003ccode\u003eX\u003c/code\u003e: Bomb \u003c/li\u003e\n\u003cli\u003e\u003ccode\u003e.\u003c/code\u003e: Empty\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eHere, 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 \u003ccode\u003eX\u003c/code\u003e ($1 \\le i, j \\le N$).\u003c/p\u003e\n\u003cp\u003eInitially, 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.\u003c/p\u003e\n\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003ccode\u003eU\u003c/code\u003e: Up\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eD\u003c/code\u003e: Down\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eL\u003c/code\u003e: Left\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eR\u003c/code\u003e: Right\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eYour 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.\u003c/p\u003e\n\u003chr\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe input consists of a single test case in the format below.\u003c/p\u003e\n\u003cblockquote\u003e$N$ $M$ $K$ $L$\n$B_{1}$\n$\\vdots$\n$B_{N}$\n$S$\u003c/blockquote\u003e\n\u003cp\u003eThe first line contains four integers $N$, $M$, $K$ and $L$($1 \\le N \u0026lt; M \\le 500$, $1 \\le K \\le L \\le 2 \\times 10^{5}$).\nThe following $N$ lines represent the bombing pattern.\n$B_i$ is a string of length $N$. Each character of $B_i$ is either \u003ccode\u003eX\u003c/code\u003e or \u003ccode\u003e.\u003c/code\u003e. The last line denotes the moving pattern. \n$S$ is a string of length $L$, which consists of either \u003ccode\u003eU\u003c/code\u003e, \u003ccode\u003eD\u003c/code\u003e, \u003ccode\u003eL\u003c/code\u003e or \u003ccode\u003eR\u003c/code\u003e. \nIt\u0027s 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.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003ePrint the number of cells which were damaged by the bomber at least $K$ times.\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cdiv class\u003d\"no-page-break\"\u003e\u003ch3\u003eExamples\u003c/h3\u003e\u003ctable class\u003d\"ioexample\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003cth\u003eInput\u003c/th\u003e\u003cth\u003eOutput\u003c/th\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cpre\u003e2 3 2 4\nXX\nX.\nRDLU\n\u003c/pre\u003e\u003c/td\u003e\u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cpre\u003e7 8 3 5\n.XXX.X.\nX..X.X.\n...XX.X\nXX.XXXX\n..XXXX.\nX.X....\n..XXXXX\nDRULD\n\u003c/pre\u003e\u003c/td\u003e\u003ctd\u003e\u003cpre\u003e26\n\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003e\u003c/p\u003e\n"}}]}