Search

A young man 'borrowed' a car and drove off to a nearby town to have some fun. What he did not know is that the car belonged to the police and carried an old tracking device. The device is outdated: it only reports the direction in which the car is moving, never how far it travels.

Given the town map, the car's initial position, and the sequence of directions it travelled, write a program that determines every position where the car could possibly have ended up.

The map is a rectangular grid. A dot (.) marks a cell the car can drive through, and an X marks a cell it cannot enter. The car's starting cell is marked with *; the car may also drive through that cell again later.

The car moves in four directions: north (up), south (down), west (left), and east (right). For each direction in the sequence, the car drives through one or more passable cells in that direction. That is, it must move at least one cell, it can never pass through or stop on an X, and it can never leave the map.

The first line contains two integers R and C ($1 \le R \le 50$, $1 \le C \le 50$), the number of rows and columns of the map, separated by a space.

Each of the next R lines contains C characters (., X, or *) describing one row of the map. Exactly one cell contains *.

The next line (line R+2) contains an integer N ($1 \le N \le 1000$), the number of directions.

Each of the following N lines contains one of the words NORTH, SOUTH, WEST, or EAST. No two consecutive directions are the same.

Print the map on R lines, in the same format as the input, where * marks exactly the cells that are possible final positions of the car. Every other passable cell must be printed as ., and every blocked cell as X. If no final position is possible, print the map with no *.