방향을 바꾸는 지렁이

지렁이 윈스턴은 여러 칸으로 나뉜 직사각형 흙밭에서 깨어난다. 각 칸에는 먹이 또는 돌이 들어 있다. 윈스턴은 어떤 칸의 먹이를 먹으며 시작한 뒤, 동서남북 네 방향 중 하나를 골라 자기 바로 앞 칸에 아직 먹지 않은 먹이가 있는 동안 일직선으로 기어가며 지나는 칸의 먹이를 모두 먹는다.

바로 앞 칸이 돌이거나, 이미 먹이를 먹은 칸이거나, 흙밭의 바깥이면 윈스턴은 왼쪽이나 오른쪽으로 $90^\circ$ 방향을 틀어 다시 일직선으로 갈 수 있는 만큼 기어가며 먹이를 먹는다. 아직 먹지 않은 먹이가 있는 칸으로만 이동할 수 있다. 같은 칸에는 두 번 들어가지 않는다. 더 이상 어느 방향으로도 갈 수 없게 되면 멈춘다.

시작 칸, 처음 방향, 그리고 막힐 때마다 어느 쪽으로 틀지를 잘 고르면 윈스턴이 먹는 먹이의 양이 달라진다. 윈스턴이 최대한 많은 먹이를 먹을 수 있도록 시작 칸과 처음 방향을 정하는 것이 당신의 과제다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 흙밭의 행과 열의 개수를 나타내는 두 양의 정수 $m$과 $n$으로 시작한다. 행과 열의 번호는 $0$부터 매긴다. 이어서 돌의 개수를 나타내는 음이 아닌 정수 $r$이 오고, 그다음 각 돌의 행과 열을 나타내는 $2r$개의 정수가 온다. $m \times n$은 $625$를 넘지 않는다. 마지막 테스트 케이스 다음에는 $0$ 두 개가 적힌 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스에 대해 테스트 케이스 번호($1$부터 시작)와 네 값을 다음 형식으로 출력한다.

Case k: amount row column direction

여기서 amount는 윈스턴이 먹을 수 있는 먹이의 최대 개수, (row, column)은 그만큼의 먹이를 먹을 수 있는 시작 칸, direction은 윈스턴이 처음 움직이는 방향으로 E, N, S, W 중 하나이다. 최댓값을 이루는 시작 칸이 여럿이면 (row, column)이 가장 작은 칸을 출력한다. 그 칸에서 여러 처음 방향이 최댓값을 이루면 E, N, S, W 순서에서 가장 먼저 오는 방향을 출력한다. 윈스턴의 시작 위치에는 항상 인접한 먹이가 적어도 하나 있다고 가정해도 된다.