Bản đồ kho báu

Bản đồ kho báu được biểu diễn dưới dạng một bảng kích thước $n\times m$ ô. Mỗi ô là một dặm vuông trên hòn đảo. Một số ô là biển và không thể đi qua. Các ô còn lại đi được; trong đó một số ô có địa danh đặc biệt (cây cổ thụ, hang động, …) được đánh dấu bằng các chữ cái in hoa khác nhau từ A đến Z.

Bản đồ đi kèm $k$ chỉ dẫn, mỗi chỉ dẫn có dạng: "Đi $\ell$ dặm về hướng $y$". Bốn hướng có thể là Bắc (N), Nam (S), Đông (E), Tây (W). Hướng Bắc là lên trên, Nam là xuống dưới, Tây là sang trái, Đông là sang phải.

Nếu xuất phát từ một ô địa danh và thực hiện đúng và đủ tất cả các chỉ dẫn theo thứ tự, đi qua chỉ các ô đi được (không được rời khỏi đảo và không được đi qua biển ở bất kỳ ô trung gian nào), thì đích đến là nơi chôn kho báu.

Vị trí xuất phát ban đầu đã bị mất, nhưng thuyền trưởng nhớ rằng nó là một ô địa danh. Hãy giúp ông liệt kê tất cả các địa danh có thể là điểm xuất phát hợp lệ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ ($3\le n,m\le 1000$).

• $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự mô tả bản đồ:

  • # — ô biển,
  • . — ô đi được không có địa danh,
  • chữ cái in hoa A–Z — ô địa danh (đi được).

  Tất cả các ô trên biên đều là #. Các địa danh đôi một được đánh dấu bằng các chữ cái khác nhau, và có ít nhất một địa danh trên bản đồ.

• Dòng kế tiếp chứa số nguyên $k$ ($1\le k\le {10}^5$).

• $k$ dòng tiếp theo, mỗi dòng chứa một chỉ dẫn dưới dạng dir len, trong đó dir thuộc {N, S, E, W} và $1\le \text{len}\le 1000$.

Dữ liệu ra

In ra một xâu gồm tất cả các chữ cái của những địa danh có thể là điểm xuất phát hợp lệ, theo thứ tự bảng chữ cái, không có dấu phân cách. Nếu không có địa danh nào phù hợp, in ra no solution.

Ràng buộc

• $3\le n,m\le 1000$
• $1\le k\le {10}^5$
• $1\le \text{len}\le 1000$
• Các ô biên đều là biển; có ít nhất một địa danh trên bản đồ.

Ví dụ