Bạn tự hào sở hữu hai rô-bốt nằm trong hai mê cung hình chữ nhật riêng biệt, mỗi mê cung không lớn hơn \(20\times20\). Ô \((1,1)\) là ô trên cùng bên trái, tức góc tây bắc. Trong mê cung thứ \(i\) có \(G_i\) lính gác, với \(0\le G_i\le10\), đi qua lại trên các đường tuần tra thẳng để bắt rô-bốt.

Đầu mỗi phút, bạn gửi cùng một lệnh cho cả hai rô-bốt. Lệnh là một hướng: bắc, nam, đông hoặc tây. Mỗi rô-bốt đi một ô theo hướng đó; nếu gặp tường thì nó đứng yên trong phút ấy. Rô-bốt thoát khỏi mê cung bằng cách đi ra ngoài biên. Khi đã thoát, nó bỏ qua mọi lệnh tiếp theo.

Lính gác cũng đi một ô vào đầu mỗi phút, đồng thời với rô-bốt. Mỗi lính gác bắt đầu tại một ô và quay mặt về một hướng cho trước. Nếu đường tuần tra có \(L\) ô, lính đi \(L-1\) bước theo hướng ban đầu, quay đầu ngay lập tức và đi ngược về ô xuất phát; tại đó lại quay đầu và tiếp tục lặp lại. Đường tuần tra không đi qua tường và không ra ngoài mê cung.

Các đường tuần tra có thể giao nhau nhưng hai lính gác không bao giờ va chạm: chúng không cùng ở một ô cuối phút và không đổi chỗ cho nhau trong một phút. Ban đầu không có lính gác nào ở cùng ô với rô-bốt.

Một lính gác bắt được rô-bốt nếu chúng ở cùng một ô vào cuối phút, hoặc đổi chỗ cho nhau trong một phút.

Hãy tìm một dãy lệnh đưa cả hai rô-bốt thoát khỏi mê cung mà không bị bắt. Cần tối thiểu hóa thời điểm rô-bốt thoát sau cùng. Nếu hai rô-bốt thoát ở hai thời điểm khác nhau, thời điểm thoát của rô-bốt sớm hơn không ảnh hưởng đến mục tiêu.

Dữ liệu vào

Trong bản luyện tập, đọc dữ liệu từ đầu vào chuẩn; tệp đầu vào trong đề gốc có tên robots.in. Dữ liệu mô tả mê cung thứ nhất rồi đến mê cung thứ hai, cùng một định dạng nhưng các giá trị có thể khác nhau:

• Dòng đầu chứa hai số nguyên \(R_i,C_i\) là số hàng và số cột, mỗi số từ 1 đến 20.
• \(R_i\) dòng tiếp theo, mỗi dòng có \(C_i\) ký tự: X là ô xuất phát của rô-bốt, . là ô trống, # là tường. Mỗi mê cung có đúng một rô-bốt.
• Dòng tiếp theo chứa \(G_i\), số lính gác.
• Mỗi trong \(G_i\) dòng tiếp theo chứa ba số nguyên và một ký tự, cách nhau bởi dấu cách. Hai số đầu là hàng và cột xuất phát của lính gác. Số thứ ba là số ô trên đường tuần tra, từ 2 đến 4. Ký tự cuối là hướng ban đầu: N, S, E, W, lần lượt là bắc, nam, đông, tây.

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn. Tệp đầu ra trong đề gốc có tên robots.out.

Nếu không có dãy lệnh hợp lệ, ghi một dòng duy nhất chứa -1.

Nếu có, dòng đầu ghi số lệnh \(K\), với \(K\le10000\). \(K\) dòng tiếp theo, mỗi dòng chứa một ký tự N, S, E hoặc W. Dãy lệnh phải đưa cả hai rô-bốt ra ngoài mà không bị bắt; lệnh cuối phải làm ít nhất một rô-bốt thoát khỏi mê cung. Nếu có lời giải thì lời giải ngắn nhất không quá 10000 lệnh. Nếu có nhiều dãy ngắn nhất, có thể ghi bất kỳ dãy nào.

Ràng buộc

Giới hạn thời gian: 2 giây CPU. Giới hạn bộ nhớ: 64 MiB.

Phân nhóm

Có 20 bộ dữ liệu, mỗi bộ tối đa 5 điểm. Với bộ dữ liệu không có lời giải, chỉ có điểm nếu trả lời đúng -1.

Với bộ dữ liệu có lời giải:

• Tính đúng đắn, 20%: kết quả đúng định dạng, không quá 10000 lệnh, cả hai rô-bốt thoát an toàn và lệnh cuối làm ít nhất một rô-bốt thoát.
• Tính ngắn nhất, 80%: ngoài các điều kiện đúng đắn trên, không tồn tại dãy hợp lệ ngắn hơn. Dãy không ngắn nhất không được phần điểm này.

Ví dụ

5 4
####
#X.#
#..#
...#
##.#
1
4 3 2 W
4 4
####
#...
#X.#
####
0

8
E
N
E
S
S
S
E
S

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 2.