Maze Construction

Time limit2sMemory limit128 MB

Summary

Simulate a sequence of forward moves and turns on a grid, then print the smallest rectangular map marking visited cells as passable and the rest as walls.

Level: Easy3 of 10
Topics: Simulation, Implementation, Matrix
Solved: No attempts yet

Problem

Hongjun is standing in one cell of a rectangular grid maze, facing south. Each cell is either passable or contains a wall. Every row and every column of the maze contains at least one passable cell.

Hongjun moved through passable cells in the maze and wrote down every action as a string. Now he wants to reconstruct the map of the maze using only that record.

Each character of the string represents one action. F means moving forward by one cell in the current direction. L and R mean turning 90 degrees left or right, respectively, without changing position.

Input

The first line contains N, the length of Hongjun's recorded string. N is greater than 0 and less than 50.

The second line contains the string of length N. The string consists only of F, L, and R.

Output

Print the smallest rectangular maze map that contains every cell Hongjun visited.

. represents a passable cell, and # represents a wall.

Examples5

Example 1
Input
```
5
RRFRF
```
Expected output
```
..
.#
```
Example 2
Input
```
6
LFFRFF
```
Expected output
```
...
##.
##.
```
Example 3
Input
```
14
LFLFRRFLFRRFLF
```
Expected output
```
#.#
...
#.#
```

Example 4

Input

19
FLFRFFRFFFRFFRFLFLL

Expected output

#..#
....
.##.
....

Example 5

Input

31
FRFFFFFFLLFRFFFFFLLFRFFFFLFFLFF

Expected output

######.
.......
#.#####
#.#...#
#.###.#
#.....#
#.#####