G. Miyamura and Cake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Miyamura has baked a yummy cake for Hori-san. He wants to paint the top of the cake, which can be represented by an $$$n$$$ by $$$m$$$ grid. Unfortunately, his only paintbrush is a cube that is colored blue on two opposite sides and red on the remaining sides. Miyamura knows that Hori-san hates blueberries, so he wants to maximize the number of red cells.

Denote the upper left corner of the cake as $$$(1, 1)$$$ and the bottom right as $$$(n, m)$$$. Miyamura can choose the starting position and orientation.

In order to color the cake, Miyamura can roll the brush onto the adjacent cells such that one edge of the cubical brush touches the cake during the duration of the roll, coloring that cell of the cake with the color of the side of the brush that lands on it.

Miyamura cannot rotate the brush and stay in the same cell, and he cannot roll the paintbrush off the canvas. If he rolls on a cell that is already covered, he will replace the color of the cell with the new color.

Your task is to help him find a sequence of moves such that all cells are colored and the number of red cells is maximized.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line and only line each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$), denoting the dimensions of the grid.

Output

The first line of each test case will have the maximum number of cells that can be painted red.

The second line will have two integers $$$a$$$, $$$b$$$ and a single character $$$c$$$ denoting the starting configuration, where:

  • $$$a$$$ ($$$1 \le a \le n$$$) represents the row number of the starting location.
  • $$$b$$$ ($$$1 \le b \le m$$$) represents the column number of the starting location.
  • $$$c$$$ represents the initial orientation of the cube. If $$$c$$$ is '-', that means that the blue sides are on the left and right side. If $$$c$$$ is '|', that means that the blue sides are on the top and bottom. If $$$c$$$ is '+', that means one of the blue sides is currently touching the cake and the other is facing upwards. Note that the starting location of the brush will be colored according to the side that is touching the cake as well.

The third line will have an integer $$$q$$$ ($$$0 \le q \le 25000$$$) denoting the number of rolls your solution performs. It is guaranteed that a sequence of operations of at most $$$25000$$$ exists to color the cake optimally.

The fourth line will contain a string of length $$$q$$$. Each character of the string is either $$$L$$$, $$$R$$$, $$$D$$$, or $$$U$$$, indicating that at that step, the cube rolled left, right, down, or up respectively.

Note that you do not need to minimize $$$q$$$. If there are multiple valid solutions, print any of them.

Example
Input
3
1 1
2 2
1 2
Output
1
1 1 |
0

3
1 1 |
5
RDLRU
2
1 1 |
1
R
Note

We use 'B' to denote the blue cells, 'R' to denote the red cells and '.' to denote the uncolored cells.

For the first testcase, the number of red cells is $$$1$$$, and the operation process can be represented as follows. 


|

For the second testcase, the number of red cells is $$$3$$$, and the operation process can be represented as follows. 


|.
..

R|
..

RR
.+

RR
-B

RR
R+

R|
RB

For the third testcase, the number of red cells is $$$2$$$, and the operation process can be represented as follows. 


|

R|