For instance, suppose Winston wakes up in the following patch of earth (X's represent stones, all other cells contain food):
If Winston starts eating in row 0, column 3, he might pursue the following path (numbers represent order of visitation):
In this case, he chose his path very wisely: every piece of food got eaten. Your task is to help Winston determine where he should begin eating so that his path will visit as many food cells as possible.
Input will consist of multiple test cases. Each test case begins with two positive integers, m and n, defining the number of rows and columns of the patch of earth. Rows and columns are numbered starting at 0, as in the figures above. Following these is a non-negative integer r indicating the number of rocks, followed by a list of 2r integers denoting the row and column number of each rock. The last test case is followed by a pair of zeros. This should not be processed. The value m x n will not exceed 625.
For each test case, print the test case number (beginning with 1), followed by four values:
amount row column direction
where amount is the maximum number of pieces of food that Winston is able to eat, (row, column) is the starting location of a path that enables Winston to consume this much food, and direction is one of E, N, S, W, indicating the initial direction in which Winston starts to move along this path. If there is more than one starting location, choose the one that is lexicographically least in terms of row and column numbers. If there are optimal paths with the same starting location and different starting directions, choose the Þst valid one in the list E, N, S, W. Assume there is always at least one piece of food adjacent to WinstonÕ initial position.
5 3 0 4 3 1 3 2 0 0
Case 1: 22 0 3 W
NOTE: problem G from 2008 East Central Regional Contest.