Pacman P30641

A pacman is moving inside an n × m rectangular board, which consists of cells with a pill, empty cells and walls. When the pacman moves into a cell (either empty or with a pill), he keeps moving in the same direction. The pacman eats the pills of the cells that he visits, so those cells become empty. Moving into a wall is forbidden: the pacman rebounds against walls, choosing any random direction (north, east, south or west) different from the current one. The pacman does all this forever.

Given a board and the initial position and direction of the pacman, can you compute which pills the pacman could eventually eat?

Input

Input consists of several cases. Each case begins with n and m, followed by n lines, each with m ‍characters: a ‘.’ for a pill, an ‘X’ for a wall. (Initially, there are no empty cells.) There is exactly one character chosen from ‘N’, ‘E’, ‘S’ or ‘W’, denoting the initial position and direction of the pacman. All the border characters are walls. You can assume 3 ≤ n, m ≤ 500.

Output

Print every board replacing by spaces the pills that could be eaten by the pacman. Print a blank line after every case.