Rolling dough is tough enough. To make a magic pizza you need to roll the magic dough on a magic board. Each magic cell on the magic board has some amount of flour. If a dough rolls over this cell, exactly 1 unit of flour stick on the dough and make the pizza more delicious. But, if a dough rolls over a cell with no flour, the dough would become terrible so don't even try it. Another tip to make a magic pizza is to follow the magic recipe, which specifies a sequence of instructions rolling the dough up, down, left and right. Once you start rolling the dough toward some directions, you should not stop unless the next cell contains no flour.
Given the initial position of the dough, the amount of flour at each cell and the magic recipe, please find out how many amount of flour stick on the dough at the end of recipe? You may assume that the cell where dough begins rolling contains at least 1 unit of flour, and one unit of flour on that cell will stick on the dough at the very beginning. Of course your dough should not fall off from the magic board.
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
For each test case, first line contains two integers m, n indicating the size of the magic board (1<= m, n<= 100). The top-left cell is numbered by (0, 0) and the bottom-right cell is (m-1, n-1). The second line contains two integers Sx, Sy denoting the starting position of the dough. Each of the next m lines contains n integers aij (0<= aij<= 100). The last line contains a string consisting of letters L, R, D, U. You may assume that the amount of flour in (Sx, Sy) is greater than 0. The length of the string does not exceed 100.
For each test case, please output the amount of flour on the dough after the last instruction.
2 5 5 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 DRULDRULDRULDRULDRU 3 6 0 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 LDRULDRULDRU
25 15
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|