Ngày xửa ngày xưa, trong Thời Đại Mộng Mơ, nước Úc là một lưới phẳng gồm \(R\) hàng và \(C\) cột, và mỗi ô lưới đều là đất. Các hàng được đánh số từ \(1\) đến \(R\) theo hướng Bắc xuống Nam, còn các cột được đánh số từ \(1\) đến \(C\) theo hướng Tây sang Đông. Ô ở hàng \(r\), cột \(c\) được ký hiệu là \((r,c)\). Một ngày nọ, con rắn cầu vồng vĩ đại trồi lên từ mặt đất tại \((s_r,s_c)\) rồi trườn khắp nước Úc, tạo ra sông ở mọi nơi nó đi qua. Con rắn thực hiện \(M\) bước di chuyển liên tiếp; tại mỗi bước, nó đi đến ô kề ngay phía Bắc (N), Nam (S), Đông (E) hoặc Tây (W) và biến ô đó thành sông. Ô \((s_r,s_c)\) cũng được biến thành sông.

Hàng triệu năm sau, bạn muốn mua một khối ô hình chữ nhật để tưởng niệm việc con rắn cầu vồng tạo ra những dòng sông. Bạn sẽ chọn một màu cho mỗi ô đất bên trong khối chữ nhật. Bạn muốn sử dụng nhiều màu khác nhau nhất có thể, nhưng yêu cầu mọi cặp ô đất kề nhau bên trong khối đều có cùng màu. Hai ô được coi là kề nhau nếu chúng có chung một cạnh. Bạn không tô màu cho bất kỳ ô đất nào bên ngoài khối, cũng không tô màu cho các ô sông bên trong khối.

Biết các bước di chuyển của con rắn cầu vồng, với mỗi trong số \(Q\) khối ô hình chữ nhật, hãy xác định số màu khác nhau lớn nhất có thể dùng để tô các ô đất.

Chi tiết cài đặt

Thí sinh phải cài đặt hai hàm sau:

void init(int R, int C, int sr, int sc, int M, char *S);

• Trình chấm gọi hàm này đầu tiên và đúng một lần.
• R, C: số hàng và số cột của lưới.
• sr, sc: hàng và cột nơi con rắn trồi lên từ mặt đất.
• M: số bước di chuyển của con rắn.
• S: chuỗi độ dài \(M\); với mọi \(0 \le i \le M - 1\), S[i] là một trong các ký tự N, S, E, W, cho biết bước thứ \(i\) của con rắn đi đến ô kề ngay phía Bắc, Nam, Đông hoặc Tây so với vị trí hiện tại. Có thể giả sử con rắn không bao giờ rời khỏi lưới.
• Hàm này không trả về giá trị.

int colour(int ar, int ac, int br, int bc);

• Sau khi gọi init một lần, trình chấm gọi hàm này liên tiếp đúng \(Q\) lần.
• ar, ac: hàng và cột của góc Tây Bắc của khối chữ nhật.
• br, bc: hàng và cột của góc Đông Nam của khối chữ nhật.
• Có thể giả sử \(1 \le ar \le br \le R\) và \(1 \le ac \le bc \le C\).
• Hàm phải trả về một số nguyên duy nhất: số màu khác nhau lớn nhất có thể dùng cho các ô đất trong khối chữ nhật từ góc Tây Bắc \((ar,ac)\) đến góc Đông Nam \((br,bc)\) theo các quy tắc trên.

Hãy tham khảo các tệp mã mẫu được cung cấp để biết thêm chi tiết về cách cài đặt lời giải bằng ngôn ngữ lập trình đã chọn.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): bốn số nguyên \(R\), \(C\), \(M\) và \(Q\).
• Dòng \(2\): hai số nguyên \(s_r\) và \(s_c\).
• Dòng \(3\): chuỗi \(S\) gồm \(M\) ký tự, mỗi ký tự là N, S, E hoặc W; để trống dòng này nếu \(M = 0\).
• Các dòng từ \(4\) đến \(Q + 3\): bốn số nguyên \(a_r\), \(a_c\), \(b_r\) và \(b_c\).

Phiên làm việc mẫu và giải thích

Các hình sau tương ứng với phiên làm việc mẫu trên. Những ô màu xanh lam có hoa văn là ô sông.

{{asset:apio17rainbow/sample-diagrams.png}}

6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

0
2
1
3

Phản hồi cho testcase mẫu này sẽ được cung cấp dưới dạng "Sample Data" khi nộp bài.

Phân nhóm

Trong tất cả các subtasks, \(0 \le M \le 100\,000\) và \(R,C,Q \ge 1\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2017: Land of the Rainbow Gold.