Maximizing Box Moves in the Push-Box Game

Together with robot β, who follows a prescribed movement string, robot α must design an \(n \times m\) grid map for a push-box game. The map is built from exactly four characters:

• |: a wall that the robot cannot pass;
• X: the starting position of the robot (and appears exactly once);
• S: a box’s initial position;
• .: an empty cell.

Outside the grid is considered to be walls. In the game, robot β starts at the cell marked X with an initial facing upward. It then follows a move string consisting of the characters:

After robot β has completed its moves, every box that was initially placed (S) must have been pushed (i.e. the robot must have encountered and moved the box from its initial location). Robot α’s goal is to maximize the number of boxes placed in the grid while ensuring that every move made by β is legal.

Your task is to design a program that, given the grid dimensions and robot β’s move string, constructs an \(n \times m\) map. For maximal box count, you should set up every forward move (W) as a push move whenever possible. That is, when a forward move is executed, if no prior requirement prevents it, the cell the robot is about to enter is set to a box (S) and its corresponding push destination cell is forced to be empty (.). For a backward move or when a conflict arises (for example, when a cell is required to be empty by an earlier push destination), you must leave the cell empty (.). The rest of the cells that are not involved in β’s trajectory should be filled with walls (|).

Note on the simulation:

• The robot starts at X facing up.
• When executing a forward move W, if the cell in front is not already forced to be empty, mark it as a box (S) and force the cell immediately beyond (in the same direction) to be empty (.). If that cell was already forced to be empty then leave it as empty.
• For a backward move (S), force the cell behind to be empty.
• All cells on which robot β lands are considered visited and must be empty (.), except if they were initially set as a box by a push move. The starting cell always remains as X.

You may assume that the input will be such that a valid construction exists (i.e. the entire simulated trajectory, after a suitable translation, fits within an \(n \times m\) grid).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of rows and columns of the grid.

The second line contains a non‐empty string representing robot β’s move sequence. The string consists only of the characters W, S, A, and D.

outputFormat

Output the constructed grid map. The output should consist of \(n\) lines with \(m\) characters each. Each character must be one of |, X, S, or . as described above.

sample

5 5
W

.||||
S||||
X||||
|||||
|||||