There are exactly $$$n$$$ cities in Byteland. The country is governed by a president, and there are exactly $$$a_i$$$ ministers in the city number $$$i$$$, which we will call the size of the ministry of this city. In any particular city, the ministers are numbered consecutively with positive integers starting from $$$1$$$ to $$$a_i$$$.
Today, the president decided to find out how many ministers there are in Byteland. To do this, he can make two types of queries:
Help the president determine how many ministers there were in Byteland in the beginning, meaning that even if their number decreases during the process of finding the answer, the president wants to know how many there were initially. Of course, the president's time is very valuable, so he can not make more than $$$q$$$ queries.
The first input line contains an integer $$$t$$$ — the number of data sets in the test ($$$1 \le t \le 5$$$). It is guaranteed that in all tests except for the example $$$t = 5$$$.
The second input line contains three space-separated integers $$$n$$$, $$$h$$$, and $$$q$$$ — the number of cities, the limit on the number of ministers in each city, and the limit on the number of queries ($$$1 \le n \le 5000$$$; $$$1 \le h \le 10^6$$$; $$$1 \le q \le 24\,000$$$). These constraints apply to all data sets in the current test.
After that, the interaction protocol with the interactor is launched $$$t$$$ times.
When your program is ready to give an answer to the problem, it should output "! A" (without quotes), where $$$A$$$ is the presumed answer. After that, the program should move on to the next set of data or terminate according to the rules described in the next section.
The interactor expects your program to make requests of three types: "- i x", "? i", and "! a", where $$$i$$$, $$$x$$$, and $$$A$$$ are integers ($$$1 \le i \le n$$$; $$$0 \le x \le h$$$). Each request should be followed by a newline character. If your program does not comply with the request format, it may receive an arbitrary verdict (other than OK).
In response to a request of the first type, the interactor replies on a new line with "OK" if the operation was successful or "FAIL" if there were less than $$$x$$$ ministers in the $$$i$$$-th city. In response to a request of the second type, the interactor also responds on a new line with the number of cities in which there are no less ministers than in city $$$i$$$.
A request of the third type means that your program is ready to give an answer to the problem. If $$$A$$$ is the correct answer, the interactor will output "OK" and move on to the next test in this multi-test or terminate if there is none. If the answer is incorrect, the interactor outputs "-1" and terminates with the verdict WA.
Your program can make no more than $$$q$$$ requests of the first or second type. The request of the third type (answer to the test) is not counted towards this limit. If this limit is exceeded, the interactor outputs "-1" and terminates with the verdict WA.
Note that the termination of the interactor means that the following tests of this multi-test will be skipped. To avoid receiving the TL or IL verdicts in this case, your program must terminate with a zero exit code when reading the value "-1" from the input.
In this problem, there are 25 tests, in addition to the example test. Each test is evaluated independently according to the criteria below, and is worth a maximum of 4 points. The input constraints used in each test are specified in the table at the end of this section.
Points for a test are awarded only if the correct answer was given on each of the $$$t$$$ data sets without exceeding the query limit. In this case, the score for each dataset is calculated according to the formula $$$$$$\mathtt{score}\left(c, j\right) = \max\left(1,\: 4 - \left\lfloor\max\left(0, \frac{c - j}{\gamma}\right)\right\rfloor\right)$$$$$$ where $$$c$$$ is the number of iterations performed by your program, $$$j$$$ is the number of iterations performed by the jury's solution, and $$$\gamma$$$ is a parameter separately specified for each test.
The final score for a test is the minimum of the $$$t$$$ scores for its data sets.
| Test number | $$$n$$$ | $$$h$$$ | $$$q$$$ | $$$\gamma$$$ | Extra constraints |
| 2 | 10 | 10 | 24 000 | 12 000 | - |
| 3 | 20 | 1000 | 20 000 | 6000 | - |
| 4 | 1000 | 20 | 20 000 | 4000 | - |
| 5 | 1000 | 100 | 6 000 | 2000 | The sizes of the ministries in different cities do not exceed $$$50$$$ distinct values |
| 6 | 5000 | 500 | 6000 | 5 | - |
| 7 | 5000 | 5000 | 15 000 | 100 | - |
| 8 | 1800 | 20 000 | 24 000 | 250 | The sizes of ministries in any two different cities differ by at least $$$5$$$ |
| 9 | 100 | 1000 | 1000 | 300 | - |
| 10 | 500 | 1 000 000 | 10 000 | 2500 | - |
| 11 | 300 | 800 000 | 4000 | 600 | The geometric mean of the sizes of the ministries does not exceed $$$20$$$ |
| 12 | 350 | 1 000 000 | 5000 | 700 | The geometric mean of the sizes of the ministries does not exceed $$$35$$$ |
| 13 | 100 | 200 | 380 | 1 | - |
| 14 | 100 | 5000 | 700 | 10 | - |
| 15 | 2000 | 500 000 | 10 000 | 100 | - |
| 16 | 100 | 10 000 | 1000 | 50 | - |
| 17 | 2000 | 500 000 | 10 500 | 150 | - |
| 18 | 2000 | 1 000 000 | 10 030 | 50 | - |
| 19 | 2000 | 1 000 000 | 10 030 | 20 | - |
| 20 | 100 | 1 000 000 | 1820 | 5 | - |
| 21 | 200 | 1 000 000 | 3420 | 15 | - |
| 22 | 200 | 1 000 000 | 3420 | 5 | - |
| 23 | 50 | 1 000 000 | 1000 | 30 | - |
| 24 | 360 | 1 000 000 | 6500 | 20 | - |
| 25 | 720 | 1 000 000 | 12 000 | 30 | - |
| 26 | 900 | 1 000 000 | 14 000 | 40 | - |
1 3 3 6 3 OK OK 3 FAIL OK OK
? 1 - 1 1 - 2 3 ? 1 - 3 3 - 3 2 ! 6
This is an interactive problem. When using buffered output, do not forget to flush the buffer when outputting requests (sys.stdout.flush() in Python, System.out().flush() in Java, and std::cout.flush() in C++).
In the example from the statement, the following actions occur:
Thus, the answer to the test from the statement is $$$1 + 3 + 2 = 6$$$. Note also that $$$q = 6$$$, and exactly $$$6$$$ queries of the form - and ? were made, while the ! query is not counted in this number.
