As you are studying ancient greek mythology, you stumble upon the legend of Phaethon, son of Helios. After being recognized by Helios as his son, he asks him to drive his chariot. Despite the warnings of Helios that only he can control the horses, Helios obliges, giving Phaethon the control of the chariot.
Tragically, Phaethon loses control of the chariot, which gets too close to the Earth and burns it.
However, you wonder if maybe the story could have ended differently. If Phaethon reaches the temple of Helios, then the chariot can be stopped by Helios himself. For that, you create a model that fits the story.
Greece can be represented as a 2D infinite grid, with Phaethon and its chariot starting at coordinate $$$(0,0)$$$, facing the Ox axis in the direction of increasing X. The temple of Helios is placed in an unknown position $$$(X,Y)$$$ on this 2D grid. Initially, the velocity V of the chariot is 1.
At each timestep, the following happens in order:
- Phaethon does one of the following 3 actions: turn the chariot left 90 degrees, continue facing front, or turn the chariot right 90 degrees;
- The chariot moves V units in the direction it is facing;
- $$$V$$$ is increased by 1;
- The Oracle tells Phaethon the Manhattan distance between his position and the position of the temple of Helios.
The Manhattan distance between $$$(X1,Y1)$$$ and $$$(X2,Y2)$$$ is $$$|X1-X2|+|Y1-Y2|$$$.
If the velocity ever reaches $$$2 \times 10^4$$$, the chariot gets uncontrolled and too close to the earth. If at the end of a step, the chariot is in $$$(X, Y)$$$, the chariot is stopped.
Input and Output
This is an interactive problem. As such, no initial input is provided in this problem, and you get to ask a question first.
At each step, you must print a line to act on the direction of the chariot. This line must follow the description "? c" followed by a newline, where c is either L to rotate counterclockwise, R to rotate clockwise, or F to keep the direction unchanged. If it does not respect this format, you will receive a WRONG-ANSWER verdict.
After sending a line, you must always flush the output. Otherwise, you will get the verdict TIMELIMIT.
The oracle then prints a single integer, that you can read on the standard input, denoting the Manhattan distance between your new position (after moving V units in the specified direction) and the temple. V is increased after updating your position.
If this distance is $$$0$$$, it means you arrived to the temple of Helios and thus should stop interaction immediately (exiting your program), receiving an ACCEPTED verdict.
Notice that you must be in the temple after your move, just flying above the temple with the chariot does not count.
If your velocity ever reaches $$$2 \times 10^4$$$, you will receive the verdict WRONG-ANSWER.
Limits
- $$$|X| \leq 10^6$$$
- $$$|Y| \leq 10^6$$$
- $$$|V| \leq 2 \times 10^4$$$
5 3 0
? F ? L ? F
In this section, to clarify what the input and output should be, "< " is printed before what your program can read on standard input and "> " is printed before what your program should output. Do not include these characters in your real input/output.
In this example, the temple of Helios (whose position you must guess) is located at X=1, Y=5. The left column is the I/O. The right column is the state of the chariot after the requested move happened.
| > ? F | Chariot moves to (1, 0), orientation = right, $$$V$$$ = 2 |
| < 5 | Distance from (1,0) to (1,5) is 5 |
| > ? L | Chariot moves to (1, 2), orientation = up, $$$V$$$ = 3 |
| < 3 | Distance from (1,2) to (1,5) is 3 |
| > ? F | Chariot moves to (1, 5), orientation = up, $$$V$$$ = 4 |
| < 0 | Success |
An interactive Python script where you can enter commands and see how the judge would respond is also available on the Web version of this problem.
