Nautilus là một tàu ngầm bí mật, di chuyển trên đại dương và cố gắng không để bị phát hiện.

Đại dương được mô hình hóa bằng một lưới gồm \(R\times C\) ô, trong đó ký tự # biểu diễn đảo và ký tự . biểu diễn nước. Chẳng hạn:

...##....
..#.##..#
..#....##
.##...#..
....#....

Mỗi phút, Nautilus phát ra một tín hiệu vô tuyến có thể tiết lộ hướng mà tàu ngầm sắp di chuyển. Hướng di chuyển luôn là một trong bốn hướng: Bắc (N), Đông (E), Nam (S), Tây (W), như trong hình dưới đây.

Vytautas đã chế tạo một ra-đa thu được các tín hiệu định kỳ của tàu ngầm. Trong \(M\) phút vừa qua, ra-đa đã thu được \(M\) tín hiệu, được biểu diễn bằng một xâu gồm \(M\) ký tự, chẳng hạn WS?EE??. Một số tín hiệu không giải mã được và được đánh dấu bằng ký tự ?.

Vytautas không biết vị trí ban đầu của tàu ngầm, nhưng muốn dùng bản đồ đại dương để xác định vị trí hiện tại của nó. Biết rằng Nautilus luôn ở trong các ô nước trên bản đồ, hãy giúp Vytautas tính số ô phân biệt mà Nautilus có thể đang ở đó.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(M\).

\(R\) dòng tiếp theo tạo thành một lưới \(R\times C\) gồm các ký tự # và ., biểu diễn bản đồ đại dương.

Dòng cuối cùng mô tả các tín hiệu Vytautas thu được: một xâu gồm \(M\) ký tự, mỗi ký tự thuộc tập N, E, S, W, ?.

Dữ liệu ra

In một số nguyên duy nhất: số vị trí hiện tại phân biệt có thể có của Nautilus.

Ràng buộc

\(1\le R,C\le 500\); \(1\le M\le 5000\).

Phân nhóm

1. Nhóm 1 (29 điểm): \(1\le R,C,M\le 100\); không có ký tự ?.
2. Nhóm 2 (37 điểm): \(1\le R,C,M\le 100\).
3. Nhóm 3 (34 điểm): \(1\le R,C\le 500\); \(1\le M\le 5000\).

Ví dụ

5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??

22

Nguồn

Baltic Olympiad in Informatics 2019, ngày 1, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.