수색

한 청년이 자동차를 '빌려' 이웃 마을로 놀러 나갔다. 그런데 그 차는 사실 경찰의 차량이었고, 오래된 추적 장치가 달려 있었다. 이 장치는 낡아서 자동차가 움직이는 방향만 알려 줄 뿐, 이동한 거리는 전혀 알려 주지 않는다.

마을 지도, 자동차의 처음 위치, 그리고 자동차가 이동한 방향의 순서가 주어질 때, 자동차가 최종적으로 있을 수 있는 모든 위치를 구하는 프로그램을 작성하여라.

지도는 직사각형 격자이다. 점(.)은 자동차가 지나갈 수 있는 칸을, X는 지나갈 수 없는 칸을 나타낸다. 자동차의 처음 위치는 *로 표시되며, 자동차는 이후에 이 칸을 다시 지나갈 수도 있다.

자동차는 북(위), 남(아래), 서(왼쪽), 동(오른쪽) 네 방향으로 움직인다. 주어진 방향의 순서대로, 각 방향마다 자동차는 그 방향으로 지나갈 수 있는 칸을 하나 이상 지난다. 즉 반드시 한 칸 이상 이동하며, X 칸을 지나거나 그 칸에 멈출 수 없고, 지도 밖으로 나갈 수도 없다.

첫째 줄에 지도의 행과 열의 수 R과 C가 공백으로 구분되어 주어진다 ($1 \le R \le 50$, $1 \le C \le 50$).

다음 R개의 줄에는 각각 C개의 문자(., X, *)가 주어져 지도의 각 행을 나타낸다. *는 정확히 한 칸에만 있다.

그다음 줄(R+2번째 줄)에는 방향의 개수 N이 주어진다 ($1 \le N \le 1000$).

이어지는 N개의 줄에는 각각 NORTH, SOUTH, WEST, EAST 중 하나가 주어진다. 연속한 두 방향은 서로 다르다.

입력과 같은 형식으로 R개의 줄에 지도를 출력한다. 이때 *는 자동차가 최종적으로 있을 수 있는 위치만을 나타낸다. 그 밖의 지나갈 수 있는 칸은 모두 .로, 지나갈 수 없는 칸은 X로 출력한다. 가능한 최종 위치가 하나도 없으면 * 없이 지도를 출력한다.