얼음판 위의 자동차

크리스마스 밤에 은행을 지키는 일은 지루하다. 그래서 배리는 주차장에서 잠깐 스케이트를 타기로 했다. 그런데 주차장은 비어 있지 않고 다른 경비원의 자동차가 세워져 있다. 배리는 그 차를 모두 주차장 밖으로 밀어내려고 한다.

각 자동차는 북, 남, 동, 서 중 한 방향을 바라보고 서 있고, 바라보는 방향으로만 밀 수 있다. 주차장 바닥은 얼어 있어서 차를 한 번 밀면 주차장을 벗어나거나 다른 차에 부딪힐 때까지 미끄러진다. 배리는 차를 한 대씩 밀고, 어떤 차도 부딪히게 하지 않으려고 한다. 따라서 어떤 차를 밀려면 그 차가 바라보는 방향으로 주차장 경계까지 놓인 칸이 모두 비어 있어야 한다. 밀린 차는 주차장을 벗어나 사라지므로 남은 차를 막지 않는다.

주차장의 상태가 주어질 때, 모든 차를 부딪히지 않게 밀어내는 순서를 구하는 프로그램을 작성하시오.

첫째 줄에 주차장의 행 수 $N$과 열 수 $M$이 공백으로 구분되어 주어진다 ($1 \le N, M \le 2000$).

다음 $N$개 줄에는 주차장의 상태가 각 줄에 $M$개의 문자로 주어진다. '.'은 빈 칸이고, 'N', 'S', 'E', 'W'는 각각 북쪽, 남쪽, 동쪽, 서쪽을 바라보는 자동차다. 북쪽은 행 번호가 작아지는 방향, 남쪽은 행 번호가 커지는 방향, 동쪽은 열 번호가 커지는 방향, 서쪽은 열 번호가 작아지는 방향이다.

차를 밀어내는 순서대로 한 줄에 한 대씩 (r,c) 형식으로 출력한다. 괄호 안에 공백을 넣지 않는다. $r$은 위에서부터 0부터 세는 행 번호, $c$는 왼쪽에서부터 0부터 세는 열 번호다. 왼쪽 맨 위 칸이 $(0,0)$, 오른쪽 맨 아래 칸이 $(N-1, M-1)$이다.

밀어내는 순서가 여럿일 수 있으므로 다음 규칙으로 하나를 정한다. 매 단계에서 지금 밀 수 있는 차 중 행 번호가 가장 작은 차를 밀고, 그런 차가 여러 대면 그중 열 번호가 가장 작은 차를 민다. 이 규칙으로 얻은 순서가 사전순으로 가장 앞선 순서다.

모든 차를 밀어낼 수 있는 순서는 항상 존재한다. 차가 한 대도 없으면 아무것도 출력하지 않는다.