Snake

In the popular game of Snake, the snake travels across a two-dimensional board, trying to eat as many apples as possible without letting its head hit a wall (the edge of the board) or its own body. To make things harder, the snake's body grows by one cell with every apple it eats.

A programmer is writing their own version of this game and needs your help. They need a program that, for a given run of the game, reports the move on which the game ends, that is, the move on which the snake's head hits its own body or a wall.

At the start the snake has length $1$ (so it occupies a single cell), but the moment it reaches a cell holding an apple, it grows by $1$.

Every move begins by advancing the snake's head. If the new position lies outside the board or is occupied by the snake's body, the game ends. If instead the new head position holds an apple, the apple is eaten (it disappears from the board) and the move is finished. Otherwise the tail is also advanced, so that the snake keeps the same length.

The first line of standard input contains three integers $n$, $m$, and $r$ ($1 \le n, m \le 1000$, $0 \le r \le 10^6$), separated by single spaces, giving the number of rows and columns of the board and the number of moves performed, respectively.

The second line contains a single letter giving the direction in which the snake starts moving. N means north, S means south, W means west, and E means east (see the figure).

The next $n$ lines describe the board. The $i$-th of these lines contains $m$ characters describing the cells of row $i$. A dot (.) is an empty cell, the letter W is the snake's starting position, and the letter J is a cell holding an apple. You may assume the board contains exactly one cell marked W.

The last line contains $r$ letters separated by single spaces, representing the snake's successive moves. N means move one cell forward, L means turn left and move one cell forward, and P means turn right and move one cell forward.

Possible initial directions of the snake's movement.

If the snake never hits its own body or the edge of the board during the $r$ moves, your program should print the single word OK to standard output. Otherwise it should print a single integer equal to the number of the move on which the snake's head hits its body or the edge of the board (moves are numbered from $1$).