끈기가 가장 적게 드는 길

밥 로버츠는 파티용 게임을 만드는 회사를 운영한다. 그가 아끼는 상품 중 하나가 퍼즐 미로다. 직사각형 격자의 칸마다 퍼즐이 하나씩 놓여 있고, 퍼즐을 풀면 다음에 갈 칸이 정해진다. 플레이어는 항상 왼쪽 위 칸에서 출발해 오른쪽 아래 도착 칸에 이를 때까지 퍼즐을 계속 푼다.

칸의 답은 rD 꼴이다. r은 이동할 칸 수, D는 방향이며 N은 위, S는 아래, E는 오른쪽, W는 왼쪽이다. 도착 칸에는 퍼즐이 없다. 이동한 자리가 격자 밖이면 경로는 거기서 끊겨 도착 칸에 이르지 못한다. 이미 지나온 칸을 다시 밟으면 같은 순환을 영원히 돌아 이때도 도착하지 못한다. 경로의 길이는 그 경로에서 푼 퍼즐의 수, 즉 이동 횟수다.

밥의 배치 프로그램에 결함이 있어서 경로가 지나치게 길거나 도착 칸에 닿지 않는 격자가 자주 나온다. 퍼즐 하나를 고치는 데 품이 많이 들어서 밥은 많아야 한 칸의 답만 바꾸려 한다. 새 답도 rD 꼴이어야 하고 r은 1 이상의 정수다.

칸을 (행, 열)로 나타내고 행과 열은 0부터 센다. 예를 들어 첫 행의 답이 2E, 2S, 1S이고 둘째 행이 1S, 1N, 1W, 셋째 행이 2N, 1E인 $3 \times 3$ 격자를 보자. 도착 칸에는 답이 없다. 경로는 (0, 0)에서 (0, 2), (1, 2), (1, 1), (0, 1), (2, 1), (2, 2)로 이어져 퍼즐 6개를 풀므로 길이는 6이다. (0, 0)의 답을 1E로 바꾸면 경로는 (0, 0), (0, 1), (2, 1), (2, 2)가 되어 길이가 3이다. 대신 (0, 2)의 답을 2S로 바꾸면 경로는 (0, 0), (0, 2), (2, 2)가 되어 길이가 2이고, 한 칸만 바꿔서는 이보다 짧게 만들 수 없다.

격자가 주어지면 시작 칸에서 도착 칸까지의 경로가 가장 짧아지도록 답을 바꿀 칸 하나를 찾아라. 두 칸 이상을 바꿔야 도착할 수 있는 격자도 있고, 어떤 칸을 바꿔도 지금 경로보다 짧아지지 않는 격자도 있다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 격자의 행 수 n과 열 수 m이 주어진다 ($1 \le n \le 100$, $1 \le m \le 100$, $nm \ge 2$). 이어서 $nm - 1$개의 이동 지시가 맨 위 행부터 각 행을 왼쪽에서 오른쪽으로 훑는 순서로 주어진다. 각 지시는 rD 꼴이고 r은 양의 정수, D는 N, S, E, W 중 하나다. 마지막 칸인 도착 칸에는 지시가 없다. 입력에 주어진 지시가 격자 밖을 가리킬 수도 있다. 지시 사이의 줄바꿈 위치는 정해져 있지 않다.

마지막 줄에 0 두 개가 주어지면 입력이 끝난다. 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 줄은 Case k: 로 시작하며 k는 1부터 세는 테스트 케이스 번호다. 그 뒤에 다음 세 가지 중 하나를 이어 쓴다.

• 한 칸만 바꿔서는 도착 칸에 이를 수 없으면 impossible을 출력한다.
• 지금 경로가 도착 칸에 이르고 어떤 한 칸을 바꿔도 더 짧아지지 않으면 none l을 출력한다. l은 지금 경로의 길이다.
• 그 밖에는 i j rD l을 출력한다. i와 j는 답을 바꿀 칸의 행과 열이고 맨 위 행이 0, 맨 왼쪽 열이 0이다. rD는 그 칸의 새 답, l은 새 경로의 길이다.

가장 짧은 길이를 만드는 변경이 둘 이상이면 행 번호가 가장 작은 것을 고른다. 행 번호까지 같으면 열 번호가 가장 작은 것을 고르고, 그래도 같으면 1E < 1N < 1S < 1W < 2E < 2N < ... 순서에서 가장 앞서는 답을 고른다.