# Finding Zero codeforces solution – Java, Python, C++

We picked an array of whole numbers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1090≤ai≤109) and concealed exactly one zero in it! Your goal is to find the location of this zero, that is, to find 𝑖i such that 𝑎𝑖=0ai=0.

You are allowed to make several queries to guess the answer. For each query, you can think up three distinct indices 𝑖,𝑗,𝑘i,j,k, and we will tell you the value of max(𝑎𝑖,𝑎𝑗,𝑎𝑘)min(𝑎𝑖,𝑎𝑗,𝑎𝑘)max(ai,aj,ak)−min(ai,aj,ak). In other words, we will tell you the difference between the maximum and the minimum number among 𝑎𝑖ai𝑎𝑗aj and 𝑎𝑘ak.

You are allowed to make no more than 2𝑛22⋅n−2 queries, and after that you have two tries to guess where the zero is. That is, you have to tell us two numbers 𝑖i and 𝑗j and you win if 𝑎𝑖=0ai=0 or 𝑎𝑗=0aj=0.

Can you guess where we hid the zero?

Note that the array in each test case is fixed beforehand and will not change during the game. In other words, the interactor is not adaptive.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡5001≤t≤500). Description of the test cases follows.

The first and only line of each test case contains an integer 𝑛n (4𝑛10004≤n≤1000) — the length of the array that we picked.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 30003000.

Interaction

For each test case, the interaction starts with reading 𝑛n.

To make a query, print “𝑖i 𝑗j 𝑘k” (without quotes, 1𝑖,𝑗,𝑘𝑛1≤i,j,k≤n, indices must be distinct). Then you should read our response from standard input, that is, max(𝑎𝑖,𝑎𝑗,𝑎𝑘)min(𝑎𝑖,𝑎𝑗,𝑎𝑘)max(ai,aj,ak)−min(ai,aj,ak).

If the response is 1−1, it means your program has made an invalid query or has run out of tries. Your program must terminate immediately after reading 1−1, and you will get a verdict Wrong answer. Otherwise you may get any verdict, because the program will continue reading from the closed stream. Note that if the query is correct, the answer will never be 1−1 because max(𝑎𝑖,𝑎𝑗,𝑎𝑘)min(𝑎𝑖,𝑎𝑗,𝑎𝑘)0max(ai,aj,ak)−min(ai,aj,ak)≥0.

To give the final answer, print “𝑖i 𝑗j” (without the quotes). Printing the same number twice (that is, 𝑖=𝑗i=j) is allowed. Note that giving this answer is not counted towards the limit of 2𝑛22⋅n−2 queries. After that, your program must continue to solve the remaining test cases, or exit if all test cases have been solved.

After printing a query, don’t forget to output line feed and flush the output buffer. Otherwise you will get the verdict Idleness limit exceeded. To flush the buffer, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• Read documentation for other languages.

Hacks

The first line must contain an integer 𝑡t (1𝑡5001≤t≤500) — the count of test cases.

The first line of each test case must contain an integer 𝑛n (4𝑛10004≤n≤1000) — the length of the hidden array.

The second line of each test case must contain 𝑛n integers separated by spaces — 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1090≤ai≤109). There must also be exactly one zero in this array.

The sum of 𝑛n over all test cases must not exceed 30003000.

Example
input

Copy
1

4

2

3

3

2

output

Copy
? 1 2 3

? 2 3 4

? 3 4 1

? 4 1 2

! 2 3
Note

Array from sample: [1,2,0,3][1,2,0,3].