Problem F
Snow Way Out

You were having such a nice day on the slopes, until the avalanche hit! You’re okay, but your backpack with all your equipment fell out. Fortunately, you have your tracking device with you which you can use to find it, but less fortunately, it was damaged and is low on power. After inspecting the damage, you ascertain that it’s only capable of telling you whether your equipment is closer, farther, or the same distance away as the last location where you clicked the device. Moreover, it only has seven clicks remaining, and the first one is just to initialize it, so you can only get six pieces of information about the equipment’s location. You’re currently trapped in a $10 \times 10$ grid, and need to find the integer coordinates where the equipment is buried.

Interaction

Your program should first print a line of the form “$x_0\ y_0\ .$”, where $0 \leq x_0, y_0 < 10$ are integers representing the $(x, y)$-coordinates where you first click the device.

At most six interactive rounds follow, in which your program prints a line of the form “$x_i\ y_i\ ?$”, where $0 \leq x_i, y_i < 10$ are the integer coordinates where you next click the device. After each guess, your program will receive the input Closer, Farther, or Same, depending on whether the equipment is closer, farther, or the same distance from your location compared to the location of the previous click. Your device compares the Euclidean (straight-line) distance — formally, if the equipment’s location is at integer coordinates $(x_e, y_e)$, then it compares $\sqrt{\left(x_i-x_e\right)^2 + \left(y_i-y_e\right)^2}$ to $\sqrt{\left(x_{i-1}-x_e\right)^2 + \left(y_{i-1}-y_e\right)^2}$.

Your program should finish by printing a line of the form “$x_e'\ y_e'\ !$”, where $0 \leq x_e', y_e' < 10$ are integers. If these coordinates match the equipment’s location ($x_e' = x_e$ and $y_e' = y_e$), then you pass the test case.

If your program’s final output does not match the equipment’s location, or if any output does not match the given specification, it will be judged as Wrong Answer. Make sure to flush the standard output, as your solution may exceed the time limit otherwise.

0 0 .
8 4 ?

Same

1 3 ?

Same

5 0 !

6 3 .
7 9 ?

Farther

8 6 ?

Farther

2 0 ?

Same

2 4 ?

Closer

1 0 ?

Farther

2 6 !