APPROXIMATE PROBLEM WARNING

Graph

There is a grid of size N*M. Each grid could be "#" or ".". You need to find the shortest path from (1,1) to (N,M) by walking on "." only.
But you are NOT given the graph. You can only see the grids near you. That is to say, you can only see a rectangle centered at your position and has length 15. For example, if your location is (15,15) then you will only be able to know the status of grid from (8,8) to (22,22).

Interaction

The problem is interactive. In each turn, you need to print one of the four characters: "WASD" to move yourself. Then you will receive a 15*15 board for the sight of you. When you reach (N,M) the interaction is end and you should terminate your program immediately.

Scoring

You will get higher score if your answer is closer to the correct answer.

Note

it is sure it's possible to walk from start to end.

Example

If the graph is

#..
#.#
...

(left-down corner is 1,1 and right-up corner is n,m)
And if the user outputs "DDAWWD" it is acceptable but not best.
If the user outputs "DDD" it will get 0 point.

Constriants

n,m<=1000