Find the Lost Car

Ralph, a young man, stole a car from a small town as a joke. However, he did not realize that the car belonged to the police station and was equipped with an old device that only emits the directions of the car's movement.

The map of the town is represented as a rectangle. Each cell on the map is either drivable or not. A cell with $\texttt{.}$ represents a drivable area, while a cell with $X$ represents an area where driving is not allowed. The initial position of the car is marked with $\texttt{*}$ and is drivable.

The car can move in four directions: north (up), south (down), west (left), and east (right). Ralph's movement is described by a sequence of direction commands. For each command, the car moves in the given direction by at least one cell and may continue for several consecutive drivable cells until just before an obstacle or the boundary of the map.

Your task is to determine and display the final all possible positions of the car on the map after executing the entire sequence of commands. In the final output map, mark every cell that could possibly be the final position of the car with a $\texttt{*}$; all other drivable cells should be shown as $\texttt{.}$, and obstacles remain as $X$.

inputFormat

The input begins with two integers R and C (1 ≤ R, C ≤ 1000) representing the number of rows and columns of the map.

This is followed by R lines, each containing C characters. Each character is one of \texttt{.} (drivable), X (non-drivable), or \texttt{*} (the initial position of the car, which is drivable). It is guaranteed that there is exactly one \texttt{*} in the map.

The next line contains an integer K (number of commands, 1 ≤ K ≤ 1000).

The last line contains K space-separated characters. Each character is one of: N, S, W, E, representing the direction (north, south, west, east) in which the car moves.

outputFormat

Output the final map after processing all commands. The map should consist of R lines with C characters each. Mark each cell that can possibly be a final position of the car with \texttt{*}, drivable cells (that are not possible final positions) with \texttt{.}, and obstacles remain as X.

sample

4 5
..X..
..X..
*....
.....
2
E S

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