21063번 - Display of Springs 다국어인터랙티브

Elater is a great magician. His most famous show is "Elater's Super Spectacular Display of Springs". The show consists in the following:

There are $n$ elastic springs in a line attached to the ceiling. Spring $i$ is attached at height $h_i$ and has a stiffness constant $k_i$. If we attach a weight of mass $w$ to the lower end of the $i$-th spring, the weight will descend to a height $H$ given by the formula:

$$H = h_i - \frac{w}{k_i}\text{.}$$

Elater will take questions from people in the audience. When asked about a positive integer $w$, Elater will be able to pick the spring which, if a weight of mass $w$ is attached to its lower end, will descend to a height lower (closer to the floor) than all the other springs (in case of a tie, he will be able to pick one of the springs with the lowest descend height). To accomplish such an amazing feat, Elater has the help of his dear assistant, Hooke.

Before the show, Hooke has some time to do measurements on the springs. He can not directly measure the values of $h_i$ and $k_i$, but he can choose two springs $a$ and $b$ and a mass $w$, try attaching a weight of mass $w$ to the two springs, and see which of them goes closer to the floor with that weight. Before the show, he has time to do up to $20\,000$ such measurements. Also, after each question, Elater can distract the audience for a while, so that Hooke can do up to $20$ more measurements before inconspicuously whispering the answer to Elater.

Can you help Hooke make the show successful? Assume that the springs are attached high enough, and the masses are small enough, so that the weights never reach the floor during any possible measurement. Also note that the weights are removed after each measurement.

First, you must read a single line with the integer $n$ ($2 \leq n \leq 500$) from the input.

To make a measurement, you must print a single line formatted as "? $a$ $b$ $w$", where $a$ and $b$ ($0 \leq a, b \leq n - 1$) are the indices of the two springs you want to use, and $w$ ($1 \leq w \leq 10^5$) is the integer weight you want to put in both springs. After that, you must read from the input a single line with the answer, which will be the word "FIRST" if spring $a$ reaches lower height, "SECOND" if spring $b$ reaches lower height, or "EQUAL" if both reach the same height.

During the first stage, you can make at most $20\,000$ measurements. After doing all the measurements of the first stage, print a single line with a single character "!". After that, you will be given one or more questions.

Each question is given on a single line formatted as "QUESTION $w$" where $w$ is the integer weight Elater is asked about ($1 \leq w \leq 10^5$). After reading each question, you can do at most $20$ measurements, in the same format as in the first stage. Once you have done the measurements, output a single line formatted as "! $i$", where $i$ ($0 \le i \le n - 1$) is the index of the spring that is the answer to the question. If there are multiple springs that reach the same minimum height, you may print any of them. 

After all questions, instead of the next one, you will get a single line consisting of the word "FINISH". It means there are no more questions and your program must finish. The total number of questions will be at least $1$ and at most $1000$.

Don't forget to flush the output after printing each line!

In each test, the values of $h_i$, $k_i$, and the questions are all fixed in advance.