종석이는 Starship-Planet의 연기 캠프에 참가하게 되었다.

종석이는 점심시간이 되어 연습실에서 식당으로 가려고 한다. 캠프장은 가로 N칸, 세로 N칸의 격자로 되어 있으며, 몇몇 칸에는 장애물이 있어서 종석이가 갈 수 없다.

캠프장의 정보가 주어질 때, 종석이가 연습실에서 식당으로 가면서 항상 가는 곳을 구하는 프로그램을 작성하여라. 단, 한 격자에서 인접한 동, 서, 남, 북 네 격자로만 갈 수 있다.

입력 형식

• 첫 번째 줄에는 캠프장의 크기 N이 입력된다. (2 ≤ N ≤ 50)
• 두 번째 줄에서 차례로 N개의 줄에는 각각의 격자에 대한 정보가 공백 없이 입력한다. 이 때, '.'은 빈 곳, ‘#'는 장애물, 'S'는 연습실, 'E'는 식당이다. 종석이가 강의실에서 식당으로 갈 수 없는 데이터는 들어오지 않는다.

출력 형식

입출력 예

입력

5
S.#..
#....
...#.
..#..
##E..

출력

So#..
#oooo
...#o
..#.o
##Eo.

예제 설명

어떻게 가도 종석이는 회색으로 색칠된 곳은 모두 가게 되어 있다.

출처:functionx