Problem G

Since his computer is his best friend, he figures that he needs a program drawing the mazes for him. So he starts thinking about an algorithm performing this difficult task for him and he comes up with 'Johnny's Simple Algorithm.'

Johnny's Simple Algorithm

 _ _ _ _
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|

After choosing the dimensions of the maze, you choose a starting cell. From now on you keep track of a list of pending cells, which initially contains only one cell (the starting cell), and you repeat the following steps:

1. If the list is empty, you stop. The maze is ready.
2. Else, you consider the most recently added cell in the list (call this cell AC). If this cell (at the end of the list) has no unvisited neighbor cells then you remove this cell from the list. Every cell has at most 4 neighbor cells: on the right, left, above and below. A cell is unvisited if it has never been added to the list.
3. If AC has at least one unvisited neighbor cell, you choose one of the unvisited neighbor cells (call this cell NC), remove the wall between AC and NC and add NC to the end of the list.

Johnny makes a nice little program using this algorithm and it works fine, but Johnny is not completely satisfied with the results. He is a demanding little boy and in his opinion the so-called branching factor of the maze is too low, i.e. the generated mazes contain very long paths and too few crossings. Therefore, the mazes are still too easy to solve for him.

A little trick can be applied to Johnny's Simple Algorithm, giving much better results. Johnny does not know it, but you will, since it will be explained below!

The idea behind the trick is to sometimes change the order of the cells in the list. This avoids long paths and results in more branches. Changing the order of the cells in the list is done by 'flipping' part of the list. A flip can be specified by giving the position of a cell in the list (where the first cell has position 1) and consists of reversing the sub-list starting at the specified cell and ending with the last cell in the list.

For example, if the list consists of the following cells:

(1,1) (1,2) (2,2) (3,2) (3,3)

(1,1) (3,3) (3,2) (2,2) (1,2)

Johnny's Advanced Algorithm

1. If the list of cells is empty, you stop. The maze is ready.
2. Else you consider the last cell in the list. If this cell has no unvisited neighbor cells, then you remove this cell from the list.
3. Otherwise, you read a command. If this command is:
   

   'F n'

   you flip the list, starting at position n.

   'U'

   you go up: you remove the wall between the last cell in the list and the cell above it. The cell above the last cell in the list is added to the list.

   'D'

   you go down.

   'L'

   you go left.

   'R'

   you go right.

Since you are taking part in a programming contest, we ask you to write a program generating nice mazes for Johnny, using 'Johnny's Advanced Algorithm,' to make him happy again. The maximum size of a maze is 39×39.

Input Specification

• The first line contains two integer values M and N, specifying the dimensions of the maze: the number of rows M followed by the number of columns N.
• The second line contains the coordinates of the starting point (again, row followed by column).
• The next lines each contain a command. A command is one of the upper case characters 'F', 'U', 'D', 'L,' and 'R', appearing at the start of a line. An 'F' character is followed by a space and an integer (the starting position of the flip.)

Output Specification

Example Input

2
3 3
1 1
U
U
R
D
D
R
U
U
3 4
2 1
R
U
L
F 2
R
U
R
D
D
F 4
D
L
L

Example Output

 _ _ _
|   | |
| | | |
|_|_ _|

 _ _ _ _
|_  |   |
|_ _  | |
|_ _ _|_|