Snake#11061
Rummaging through one of the chests at home, Karych found an old push-button telephone. There is only one game on this phone, but what a game! Snake! Karych used to play it a lot while, for example, riding a train or standing in a line.
The game takes place on the checkered field n \times m. The field is not looped either vertically or horizontally. That is, if the snake crashes into the field boundary, the game will end with a loss. Field rows are numbered from to from top to bottom, and columns from to from left to right.
At any given time, a snake is a sequence of cells where every two consecutive cells are side-adjacent. Each cell occurs in the sequence at most once. The first cell in the sequence is called the head of the snake, and the last cell is called the tail. Also, one of the cells of the field that does not belong to the snake contains an apple.
On each turn, the player must choose one of the four directions of movement: up, down, left, or right. After that, the game finds a cell adjacent to the head of the snake in the direction chosen by the player. Let's call it .
- If there is no cell in the chosen direction, that is, the player went beyond the boundary of the field, the game ends. - Otherwise, if there is an apple in , the snake eats it, its length increases by , and the cell is added to the beginning of the sequence of cells representing the snake. - Otherwise, the last one (the tail) is removed from the sequence of cells first. Then, if the cell still occurs in the sequence, the snake has crashed into itself, so the game is over. Otherwise, cell is appended to the start of the sequence.
Please note that because the old tail cell is removed from the sequence first, and only then the new head cell is added, after the move, the head cell can occupy the cell in which the tail was before this move.
At the beginning of the game, the snake has a length of .
Karych heard that if you win this game, that is, fill all the cells of the field with the snake, then the game will show a cartoon. But he never managed to achieve this. Help him! You must make no more than moves.
In the first line, you will be given two integers and (2 \leq n, m \leq 10)—the size of the field.
The second line contains two integers x_s and y_s (1 \leq x_s \leq n, 1 \leq y_s \leq m) —the number of the row and column where the snake is located at the start of the game.
The third line contains two integers x_a and y_a (1 \leq x_a \leq n, 1 \leq y_a \leq m) —the coordinates of the cell where the apple is located at the start of the game.
Next, you must interact with the testing program. On each turn, you must print one of the symbols indicating the direction of movement: "U" (up), "D" (down), "L" (left), or "R" (right).
Then, the program will print one of several possible answers:
- "fail" —means the snake hit the wall, ate itself, or you have no moves left but did not win. In this case, you must immediately terminate your program in order to receive a WA verdict. Otherwise, you may receive any verdict (not AC). - "win" —the length of the snake has become equal to n \times m, you have won. You must not print anything else and must terminate the program. - "ok" —you made a valid move. As a result, the head of the snake has moved in the chosen direction, and the snake's length did not change. - "new" —you made a valid move and the snake ate the apple. The head of the snake moved in the chosen direction, the length of the snake increased by . In the next line, there will be two integers x_a and y_a (1 \leq x_a \leq n, 1 \leq y_a \leq m) —the coordinates of the new apple position.
It is guaranteed that at any moment, the apple will be in a cell that does not belong to the snake.
Remember to print a newline and flush the output buffer after each output.