Trampler

Interview

Time limit2sMemory limit256 MB

Summary

For each starting cell of an H by W grid, follow a fixed move string and output the sum of visited cell times, or 0 if the path leaves the field.

Level: Medium4 of 10
Topics: Simulation, Implementation, Array, Brute force
Solved: No attempts yet

Problem

Trampler the Jackrabbit loves trampling fields. He has just found a good new field. As seen on the map, the field is a rectangle $H$ cells high and $W$ cells wide. When Trampler gets into a cell, he tramples it down to the last twig. It takes him a while to do that, and that time is defined for each specific cell.

Trampler is not sure where to begin, but he has already figured out the sequence of moves. He scribbled it down on a piece of paper, marking each elemental move with a letter.

There are different kinds of moves:

letter 'U': move from the current field cell to the cell directly adjacent above;
letter 'R': move to the adjacent cell on the right;
letter 'L': move to the adjacent cell on the left;
letter 'D': move to the adjacent cell below.

For each cell, Trampler needs to know the time necessary to implement his plan, should he begin his trampling route from that cell. He will spend some time in the initial cell and in each consecutive cell, even if that cell has already been trampled.

He is not planning to leave the field until he is done. If starting at a certain cell means having to leave the field eventually, this cell is no good for a starting point. Trampler wants such cells marked with 0.

Input

The first line of the input file defines an integer $T$ , the number of test cases ( $1 \le T \le 100$ ). It is followed by $T$ blocks.

The first line of a block contains two integers $H$ and $W$ , the height and width of the field, respectively ( $1 \le H, W \le 100$ ).

The second line of the block contains a non-empty sequence of moves. Each move is represented by one of the symbols 'L', 'R', 'U', 'D'. The number of moves is less than or equal to $100$ .

Each of the following $H$ lines contains $W$ integers: the time the jackrabbit spends in a specific field cell. These numbers fall in the range from $1$ through $1\,000$ .

The total number of cells in all test cases is less than or equal to $10^5$ .

Output

For each test case, print $H$ lines of $W$ integers: the answers for each of the field cells.

Notes

The illustration in the problem statement shows the field from the first example and the directions of moves.

Examples2

Example 1

Input

Expected output

41 38 0 0
37 33 0 0
0 0 0 0

Example 2

Input

Expected output

0
0 0 0 0 0
0 76 72 49 0
0 63 51 40 0
0 47 51 63 0
0 0 0 0 0