잘못된 안내

시간 제한2초메모리 제한1024 MB

요약

각 단계가 원래 방향이 아닌 다른 방향으로 바뀐 지시 문자열과 격자가 주어질 때, 보물이 있을 수 있는 모든 칸을 표시한다.

난이도: 어려움10점 중 8점
유형: BFS, 그래프, 구현, 행렬
정답자: 아직 제출이 없습니다

문제

먼 섬에 발이 묶인 당신은 전설 속 보물을 찾고 있다. 그런데 보물로 곧장 이어지는 안내를 손에 넣었는데도 문제가 하나 있다. 원정대에 방해꾼이 숨어 있었고, 그자가 어느 시점에 소중한 안내를 손봐서 더 이상 보물로 이어지지 않게 만들어 버린 것이다.

섬은 직사각형 격자로 나타낼 수 있고, 안내는 주어진 시작 위치에서 격자 위를 동서남북으로 움직이는 일련의 단계다. 이 안내는 장애물을 돌아가야 할 수도 있지만, 보물에 이르는 더 짧은 방법이 없다는 점에서 보물로 곧장 이어진다. 그런데 방해꾼이 각 단계를 나머지 세 방향 중 하나로 임의로 바꿔 놓았다. 다시 말해 '서' 단계는 '동', '북', '남' 중 하나로 바뀌었다. 이 교체는 단계마다 독립적으로 이루어졌으므로, 어떤 '서'는 '북'으로, 다른 '서'는 '남'으로 바뀌는 식이다.

이런 방해 때문에 안내는 쓸모없어 보인다. 그래도 수색 범위를 좁히는 데는 쓸 수 있을지 모른다. 보물이 있을 수 있는 모든 위치를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 지도의 너비와 높이를 나타내는 두 정수 $w$ , $h$ 가 주어진다( $3 \le w, h \le 1000$ ). 이어서 지도를 나타내는 $h$ 개의 줄이 각각 $w$ 개의 문자로 주어진다. 각 문자는 걸어 다닐 수 있는 공간을 나타내는 '.', 물이나 빽빽한 숲, 산처럼 지나갈 수 없는 장애물을 나타내는 '#', 안내의 시작 위치를 나타내는 'S' 중 하나다.

마지막 줄에는 'NWSE' 문자로만 이루어진 문자열 $I$ 가 주어지며, 이는 잘못된 안내 순서다( $1 \le |I| \le 10^5$ ).

지도에는 'S'가 정확히 하나 있고, 지도의 경계는 장애물 칸으로만 이루어져 있다. 잘못된 안내 순서에는 보물이 있을 수 있는 위치가 적어도 하나 있다.

출력

보물이 있을 수 있는 모든 위치를 느낌표('!')로 표시한 지도를 입력과 같은 형식으로 출력한다(크기를 나타내는 첫 줄은 제외한다).

예제2

예제 1

입력

5 5
#####
#...#
#.S.#
#...#
#####
N

예상 출력

#####
#...#
#!S!#
#.!.#
#####

예제 2

입력

7 5
#######
#..#..#
#..S..#
#..#..#
#######
ESS

예상 출력

#######
#!.#..#
#..S..#
#..#..#
#######