402819: GYM100889 C Chunin Exam

Chunin exams are going on. To pass the "Stage 2:The Forest of Death", Naruto has to reach the tower in time. As you know Naruto has very little memory. Help Naruto find his way through the forest of death.

The forest of death is N × M grid(N and M are not given in input). Rows are numbered from 1 to N in to direction and columns are numbered 1 to M in to direction. Naruto is currently at position (1, 1) and tower is at position (N, M). It is given that 1 ≤ N, M ≤ 10⁴.

P cells are dangerous for Naruto and he can't go to those cells(0 ≤ P ≤ 5 * 10⁴). Your task is to help Naruto navigate through the grid with help of a system which responds to two type of queries:

• Naruto can at four edge-adjacent cells from his current position in the grid. In response to this query, system will tell whether its safe to go to those positions. Its always unsafe to go outside the grid.
• Naruto can perform queries, which will result in Naruto moving one step from his current position to one of the adjacent safe cells. In response to such query, you will be told whether you've reached tower or not.

You are not allowed more than 12 * P + 4 * (N + M) queries. Also, note the unusual memory limit.

All lines of input stream consist of response to queries in one line.

To make a query, print a line which contains a string query. Don’t forget to put a newline character and to flush the output stream after you print your query.

Note that testing system will not provide N and M in input. Your solution asks the queries and the system answers them as given in statement.

For a query, you specify the string , where denoting the direction of adjacent square to which you want to look. In response to this query, you can read from STDIN, one of the string, or denoting whether you can go to the adjacent cell in corresponding direction or not.

For a query, you specify the string , where denoting the direction of adjacent square to which you want to go to. System will change the current position of Naruto to corresponding square and return a string or denoting whether Naruto has reached the tower or not. After receiving a , your program should exit successfully.

If your query contains wrong characters, the system will terminate the testing and you will receive the "Presentation Error" outcome.

If you perform a query which results in Naruto's position to a dangerous cell, or if you exceed the number of allowed queries, you will receive a "Wrong Answer" outcome.

You will receive the "Time Limit Exceeded" outcome and other errors for the usual violations.

Finally, if everything is OK (i.e. Naruto reaches destination) on every test, you will receive the "Accepted" outcome, in this case you will have solved the problem.

SAFE
NO
UNSAFE
SAFE
YES

LOOK RIGHT
GO RIGHT
LOOK DOWN
LOOK RIGHT
GO RIGHT

In this example, N = 1 and M = 3.

Read sample output and then system input line by line.

Naruto starts at (1, 1) and looks at (1, 2)(output line 1) which is safe(input line 1), then goes there(output line 2), where system tells that Naruto hasn't reached tower(input line 2), looks at (2, 2)(output line 3) which is unsafe(input line 3), then he looks at (1, 3)(output line 4), which is safe(input line 4), and reaches there(output line 5), which is the location of the target(input line 5).