지렁이 게임

Worm은 오래된 컴퓨터 게임이다. 여러 버전이 있지만 모두 화면 위에서 "지렁이"를 조종하며, 지렁이가 자기 몸이나 장애물에 부딪히지 않도록 하는 것이 목표다.

여기서는 아주 단순화한 버전을 시뮬레이션한다. 게임은 $50 \times 50$ 판 위에서 진행되며, 칸에 번호를 매겨 왼쪽 위 칸이 $(1, 1)$이 되도록 한다. 좌표의 첫 번째 값은 행 $r$, 두 번째 값은 열 $c$이며 $1 \le r \le 50$, $1 \le c \le 50$이다.

지렁이는 서로 연결된 20개의 칸으로 이루어진 사슬이다. 두 칸은 상하 또는 좌우로 인접할 때 연결된 것으로 본다. 처음에 지렁이는 가로로 뻗어 $(25, 11)$부터 $(25, 30)$까지를 차지하며, 머리는 $(25, 30)$에 있다.

매 이동마다 지렁이는 동(E), 서(W), 북(N), 남(S) 중 한 방향으로 한 칸 나아간다. E와 W는 열을 각각 $+1$, $-1$ 하고, S와 N은 행을 각각 $+1$, $-1$ 한다. 지렁이는 절대로 자기 몸 쪽(바로 뒤)으로 되돌아가지 않으므로, 시작 위치에서는 W 이동이 불가능하다. 그래서 한 번의 이동에서 바뀌는 칸은 머리와 꼬리 두 개뿐이다. 머리가 한 칸 나아가고 꼬리가 한 칸 앞으로 당겨진다. 특히 머리는 같은 이동에서 꼬리가 막 비운 칸으로 들어갈 수 있다.

주어진 이동 순서를 따라 다음 중 하나가 일어날 때까지 시뮬레이션한다.

• 지렁이가 자기 몸에 부딪힌다,
• 지렁이가 판 밖으로 나간다,
• 지렁이가 모든 이동을 끝마친다.

앞의 두 경우에는 남은 이동을 무시한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 주어진다. 첫 줄에는 이동 횟수를 나타내는 정수 $n$ ($n < 100$)이 주어진다. $n = 0$인 줄은 입력의 끝을 뜻하며 처리하지 않는다. 둘째 줄에는 공백 없이 정확히 $n$개의 문자가 주어지며, 각 문자는 E, W, N, S 중 하나로 이동 순서를 나타낸다.

각 테스트 케이스마다 정확히 한 줄을 출력한다. 첫 이동을 1번으로 셀 때, 직접 정한 이동 번호 $m$에 대해 다음 세 가지 중 정확히 하나여야 한다.

• The worm ran into itself on move m.
• The worm ran off the board on move m.
• The worm successfully made all m moves.