408727: GYM103274 E Escape Room

E. Escape Roomtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

A new escape room has opened in the city. In this escape room, a group of at least two people is required to play. At the beginning of the game one person of the group will be selected, this person will enter the room while others stay outside of the room with a map. The one that enters the room has a device and will be blindfolded, so, the person is not aware of the surroundings. The game is as follows, the person inside the room will use the device to tell the others in the group the coordinates $$$(i, j)$$$ the person believes is positioned in the map, the group then will answer with the steps the person should follow in order to escape the room.

The map of the room is represented by a matrix with $$$R$$$ rows and $$$C$$$ columns, each position of the matrix has a character wich means the following:

• '.' means the person can be positioned in that position.
• '#' means there is a wall at that position.
• 'X' means there is an object at that position.
• 'E' represents the position of the exit in the room.

For each coordinate the person in the room sends to the group, the group should answer with a single character:

• 'W' if the coordinate sent has a wall in the map.
• 'X' if the coordinate sent has an object in the map.
• 'E' if the coordinate sent is the exit.
• '?' If the coordinate indicates a place with no way to the exit
• An indication of the path the person should follow to get to the exit if the map has a '.' in that coordinate.

The indications of the path the group will send to the person are always in such way that if the person moves in that direction the person will be closer to the exit than before, the indication should be a character based on the move the person should perform:

• 'L' if the person should move left.
• 'D' if the person should move down.
• 'R' if the person should move right.
• 'U' if the person should move up.

If the person can move in more than one direction and get closer to the exit, the group should answer with the first from the above list that makes the person closer to the exit. People can't go through object nor walls.

Given the map of the room, and the coordinates sent by the person inside the room, write a program with the answer the group should send to the person.

Input

The first line of input contains two integers separated by a space $$$R$$$ and $$$C$$$ ($$$1 \leq R, C \leq 1000$$$), representing the number of rows and columns in the map. The next $$$R$$$ lines in the input contain $$$C$$$ characters, the $$$j$$$-th character of the $$$i$$$-th line represents the character in the map at coordinate ($$$i,j$$$). Coordinates start at (1, 1) and end in ($$$R$$$, $$$C$$$). The next line contains a single integer $$$Q$$$, the number of coordinates the person in the room will send. Each of the next $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) lines contains two integer numbers separated by a space, representing the coordinate $$$(i,j)$$$ sent by the person in the room.

Output

For each coordinate sent by the person print a line with a single character, the answer the group should send to the person.

ExampleInput

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

Output

D
E
X
W
?