뱀

유명한 뱀 게임은 2차원 판 위에서 뱀을 움직여, 머리가 벽(판의 가장자리)이나 자신의 몸에 부딪히지 않으면서 판 위에 놓인 사과를 최대한 많이 먹는 게임이다. 난이도를 높이는 요소로, 뱀은 사과를 하나 먹을 때마다 몸이 한 칸씩 길어진다.

한 프로그래머가 이 게임을 직접 만들고 있으며 도움이 필요하다. 주어진 한 판의 진행 과정에 대해, 게임이 끝나는 순간, 즉 뱀의 머리가 자신의 몸이나 벽에 부딪히는 이동이 몇 번째인지 알려 주는 프로그램이 필요하다.

처음에 뱀의 길이는 $1$이다(즉 한 칸만 차지한다). 하지만 사과가 놓인 칸에 도달하는 순간 길이가 $1$만큼 길어진다.

각 이동은 뱀의 머리를 이동시키는 것으로 시작한다. 새 위치가 판 밖이거나 뱀의 몸이 이미 차지하고 있다면 게임이 끝난다. 반면 새 머리 위치에 사과가 있으면 그 사과를 먹고(판에서 사라진다) 이번 이동은 끝난다. 그렇지 않으면 꼬리도 함께 이동하여 뱀의 길이가 이전과 동일하게 유지된다.

표준 입력의 첫 줄에는 세 정수 $n$, $m$, $r$ ($1 \le n, m \le 1000$, $0 \le r \le 10^6$)이 한 칸씩 띄어서 주어진다. 각각 판의 행 수와 열 수, 그리고 수행할 이동의 수를 뜻한다.

둘째 줄에는 뱀이 처음 움직이기 시작하는 방향을 나타내는 문자 하나가 주어진다. N은 북쪽, S는 남쪽, W는 서쪽, E는 동쪽을 뜻한다(그림 참고).

다음 $n$개 줄에는 판의 상태가 주어진다. 이 중 $i$번째 줄에는 $i$번째 행의 칸들을 나타내는 $m$개의 문자가 있다. 마침표(.)는 빈 칸, 문자 W는 뱀의 시작 위치, 문자 J는 사과가 놓인 칸을 뜻한다. 판에는 W로 표시된 칸이 정확히 하나 있다고 가정해도 된다.

마지막 줄에는 뱀의 연속된 이동을 나타내는 $r$개의 문자가 한 칸씩 띄어서 주어진다. N은 한 칸 앞으로 전진, L은 왼쪽으로 회전한 뒤 한 칸 전진, P는 오른쪽으로 회전한 뒤 한 칸 전진함을 뜻한다.

뱀이 움직일 수 있는 초기 방향.

$r$번의 이동 동안 뱀이 자신의 몸이나 판의 가장자리에 한 번도 부딪히지 않았다면 표준 출력에 OK라는 단어 하나를 출력한다. 그렇지 않으면 뱀의 머리가 자신의 몸이나 판의 가장자리에 부딪히는 이동의 번호를 정수 하나로 출력한다(이동은 $1$부터 번호를 매긴다).