Bạn thức dậy, không biết bằng cách nào, tại một nơi giống như mê cung vô tận với ánh sáng huỳnh quang mờ nhạt và bầu không khí ngột ngạt. Người ta gọi đây là The Backrooms.

The Backrooms là gì?

Bạn hoàn toàn bị mất phương hướng. Những bức tường mục nát, tiếng ù ù kỳ lạ, và sự im lặng chết chóc khiến bạn nghi ngờ mọi thứ. Bạn không đơn độc, nhưng nhóm của bạn không ở đây. Họ đang quan sát từ xa qua bản đồ. Nhiệm vụ của họ là hướng dẫn bạn tìm ra lối thoát, nhưng nơi đây có nhiều cạm bẫy:

Bản đồ của phòng được biểu diễn dưới dạng một ma trận kích thước $R$ $\times$ $C$, trong đó:

• .: Có thể đứng ở vị trí này.
• '#': Vị trí bức tường.
• 'X': Vị trí có vật cản.
• 'E': Vị trí lối thoát.

Khi nhận được một tọa độ từ người trong phòng, nhóm bên ngoài sẽ phản hồi như sau:

• 'W': Nếu tọa độ là tường.
• 'X': Nếu tọa độ là vật cản.
• 'E': Nếu tọa độ là lối thoát.
• '?': Nếu tọa độ không có đường đến lối thoát

Nếu tọa độ không thuộc các kí tự trên thì họ sẽ mô tả các hướng di chuyển như sau:

• 'L': Di chuyển sang trái.
• 'R': Di chuyển sang phải.
• 'D': Di chuyển xuống dưới.
• 'U': Di chuyển lên trên.

Nếu có nhiều hướng dẫn có thể đưa người chơi đến gần lối thoát hơn, nhóm sẽ ưu tiên lần lượt theo thứ tự: L, D, R, U. Người chơi không thể đi qua tường hoặc vật cản.

NOTE : Lưu ý căn phòng chỉ tồn tại một lối thoát duy nhất.

Input

• Dòng đầu tiên chứa hai số nguyên $R$ và $C$ $(1\le R,C\le 1000)$ - kích thước bản đồ của The Backrooms.
• Tiếp theo $R$ dòng, mỗi dòng chứa $C$ ký tự - mô tả bản đồ của phòng.
• Dòng tiếp theo chứa số nguyên $Q$ $(1\le Q\le {10}^5)$ - là số tọa độ mà người trong phòng sẽ gửi ra.
• $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ và $j$ - là tọa độ mà người trong phòng gửi ra.

Output

• Với mỗi tọa độ nhận được, in ra một dòng chứa một ký tự, là phản hồi mà nhóm sẽ gửi lại cho người trong phòng.

Sample Input 1

5 5
...##
.E..#
#.X.#
...##
...#.
5
1 1
2 2
3 3
3 1
5 5

Sample Output 1

D
E
X
W
?