Description

Young Ralph jokingly stole a car from a small town, but he did not expect that the car belonged to the police department and that it was equipped with a device that broadcasts the car’s movement route.

The device is so old that it can only broadcast the directions of the car’s movement.

Write a program to help the police department find the car using a map of the town. The program must indicate all possible final positions of the car.

The town map is rectangular, and symbols mark where driving is allowed or not. $\verb!.!$ denotes a drivable cell in the town, while $\verb!X!$ denotes a non-drivable cell. The car’s initial position is marked with the character $\verb!*!$, and that cell is drivable.

The car can move in four directions: north (up), south (down), west (left), and east (right).

The car’s route is described by a given sequence of directions. For each given direction, Ralph drives the car through one or more drivable cells of the town.

Input Format

The first line of the input file contains two natural numbers $R$ and $C$, $1 \le R \le 50$, $1 \le C \le 50$, representing the number of rows and columns of the town map, respectively.

Each of the next $R$ lines contains a sequence of $C$ symbols ($\verb!.!$ or $\verb!X!$ or $\verb!*!$) describing the corresponding part of the map.

The $(R+2)$-th line contains a natural number $N$, $1 \le N \le 1000$, representing the length of the sequence of directions.

Each of the next $N$ lines contains one of the following words: NORTH (north), SOUTH (south), WEST (west), and EAST (east), indicating the direction of movement. Any two consecutive directions are different.

Output Format

Output the town map in $R$ lines (as in the input file). The character $\verb!*!$ should be used only to denote the car’s possible final positions.

4 5
.....
.X...
...*X
X.X..
3
NORTH
WEST
SOUTH

.....
*X*..
*.*.X
X.X..

Hint

Translated by ChatGPT 5