Blindfold

Rose and Colin are playing a game in their backyard. Because the backyard is rectangular, we can view it as a grid with $r$ rows and $c$ columns. Some squares contain obstacles.

The game works as follows. Colin covers his eyes with a blindfold, and Rose carries him to some square of the backyard, setting him down so that he faces north, south, east, or west. Colin does not know this initial position or direction. Rose then tells Colin to make a sequence of $m$ moves, where each move is one of:

• F — move forward one square in the direction he is facing.
• L — turn 90 degrees counter-clockwise, staying on the same square.
• R — turn 90 degrees clockwise, staying on the same square.

After making all of these moves, Colin ends up at some final position. Determine every square that could be his final position. You may assume that Colin's initial position, final position, and all intermediate positions always lie inside the backyard and never on a square that contains an obstacle, and that Colin always faces a direction parallel to the sides of the backyard (north, south, east, or west).

The first line contains $r$ and the second line contains $c$ $(1 \le r \le 375,\ 1 \le c \le 80)$. The next $r$ lines describe the backyard, each with $c$ characters: a . denotes a square Colin may walk through, and an X denotes a square with an obstacle. The next line contains the number of moves $m$ $(0 \le m \le 30000)$, followed by $m$ lines describing Colin's moves. Each line holds a single character: F, L, or R.

Print the backyard grid as $r$ lines of $c$ characters. Mark each obstacle square with X, each square that could be Colin's final position with *, and every other walkable square with ..