로봇의 이동

로봇은 격자 위에 놓인 이동 명령을 따라 움직인다. 격자의 각 칸에는 다음에 어느 방향으로 이동할지를 알려 주는 명령이 하나씩 적혀 있다.

• N — 북쪽(위)
• S — 남쪽(아래)
• E — 동쪽(오른쪽)
• W — 서쪽(왼쪽)

로봇은 격자의 북쪽(맨 위) 경계에서 주어진 열로 진입하여, 자신이 도착한 칸의 명령을 즉시 읽고 그 방향으로 한 칸 이동한다. 그리고 새로 도착한 칸의 명령을 다시 따르는 과정을 반복한다.

결국 다음 두 가지 중 정확히 하나가 반드시 일어난다.

1. 로봇이 격자의 네 경계 중 한쪽으로 빠져나간다(탈출).
2. 로봇이 이전에 지나갔던 칸을 다시 방문한다. 이 경우 로봇은 끝없는 순환(루프)에 빠진 것이다.

각 격자에 대해, 로봇이 격자를 빠져나가기까지 몇 걸음을 이동하는지, 또는 루프에 빠지기까지 몇 걸음을 이동한 뒤 몇 걸음짜리 루프를 도는지를 구하는 프로그램을 작성하라.

입력은 하나 이상의 격자로 이루어진다. 각 격자는 다음 형식으로 주어진다.

첫 줄에는 공백으로 구분된 세 정수가 주어진다. 격자의 행 수 $R$, 열 수 $C$, 그리고 로봇이 북쪽에서 진입하는 열의 번호이다. 열은 왼쪽부터 1번으로 매긴다.

이어지는 $R$개의 줄이 격자의 각 행을 나타낸다. 각 줄은 정확히 $C$개의 문자로 이루어지며, 각 문자는 N, S, E, W 중 하나이고 공백은 없다.

모든 격자는 $1 \le R, C \le 10$을 만족한다. 입력의 끝은 0 0 0으로 이루어진 줄로 표시되며, 이 줄은 처리하지 않는다.

각 격자마다 정확히 한 줄을 출력한다.

• 로봇이 격자를 빠져나가는 경우:

  X step(s) to exit

  여기서 X는 로봇이 경계를 벗어나기 전까지 따른 명령의 수이다.

• 로봇이 루프에 빠지는 경우:

  Y step(s) before a loop of Z step(s)

  여기서 Y는 루프가 시작되기 전까지 따른 명령의 수이고, Z는 루프 한 바퀴에 포함된 명령의 수이다.

step이라는 단어 뒤에는 앞의 수가 1이든 아니든 항상 (s)가 곧바로 붙는다.