Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Chú sâu Winston di chuyển trong bản đồ kích thước m x n. Ở mỗi ô sẽ có thức ăn hoặc đá chặn. Từ vị trí xuất phát, chú sâu Winston ăn thức  ăn ở ô đang đứng rồi di chuyển theo 1 trong 4 hướng (Đông, Tây, Nam, Bắc) và sau đó đi thẳng cho đến khi nào gặp đá chặn phía trước hoặc ô phía trước đã bị ăn hết thức ăn hoặc gặp đường biên, khi đó chú sâu sẽ rẽ trái hoặc rẽ phải và tiếp tục hành trình. Mỗi khi đi qua 1 ô, chú sâu luôn ăn hết thức ăn ở ô đó. Chú sâu không bao giờ đi lại một ô đã đi và khi không thể đi được nữa, chú sâu đứng lại và kết thúc hành trình.

Ví dụ bản đồ kích thước 5 x 5 như sau, ô X là ô có đá, các ô còn lại là ô thức ăn:

Ví dụ chú sâu Winston bắt đầu từ hàng 0 cột 3 và đi theo lộ trình như sau:

Ở ví dụ này, chú sâu đã di chuyển hợp lí và ăn được hết tất cả thức ăn. Nhiệm vụ của bạn là giúp chú sâu chọn vị trí bắt đầu để chú có thể ăn được nhiều nhất thức ăn.

Input

Input gồm nhiều bộ test, mỗi bộ test bao gồm:

• Dòng đầu ghi 2 số nguyên dương m, n là số hàng và số cột (m, n £ 625)
• Dòng tiếp theo ghi số r là số đá và sau đó là 2r số nguyên cho biết tọa độ các tảng đá (chú ý: hàng và cột được đánh số từ 0).
• Input kết thúc khi gặp dòng chứa 2 số 0 0

Output

Với mỗi bộ test, in ra số thứ tự bộ test, tiếp theo là 4 giá trị:

Số lượng ăn được tối đa, hàng xuất phát, cột xuất phát, hướng

Giá trị hướng là 1 trong 4 chữ E, N, S, W tương ứng với Đông, Bắc, Nam, Tây.

Nếu có nhiều hơn 1 điểm xuất phát có thể ăn được tối đa thức ăn, hãy chọn điểm xuất phát có tọa độ hàng nhỏ hơn, nếu cùng tọa độ hàng thì chọn tọa độ cột nhỏ hơn. Nếu cùng 1 điểm xuất phát có thể đi theo nhiều hơn 1 hướng để ăn được tối đa thức ăn, chọn hướng đầu tiên trong dãy E, N, S, W.

Example

Input:
5 5
3
0 4 3 1 3 2
0 0

Output:
Case 1: 22 0 3 W