Nastia has a concealed change p of length n comprising of integers from 1 to n. You, for reasons unknown, need to sort out the change. To do that, you can give her an integer t (1≤t≤2), two unique records I and j (1≤i,j≤n, i≠j), and an integer x (1≤x≤n−1).
Correct answer will be upvoted else downvoted.
Nastia has a concealed change p of length n comprising of integers from 1 to n. You, for reasons unknown, need to sort out the change. To do that, you can give her an integer t (1≤t≤2), two unique records I and j (1≤i,j≤n, i≠j), and an integer x (1≤x≤n−1).
Contingent upon t, she will reply:
t=1: max(min(x,pi),min(x+1,pj));
t=2: min(max(x,pi),max(x+1,pj)).
You can ask Nastia at most ⌊3⋅n2⌋+30 times. It is ensured that she won't change her stage contingent upon your questions. Would you be able to figure the change?
Input
The input comprises of a few experiments. First and foremost, you get the integer T (1≤T≤10000) — the number of experiments.
Toward the start of each experiment, you get an integer n (3≤n≤104) — the length of the change p.
It's reliable that the change is fixed ahead of time and that the amount of n in one test doesn't surpass 2⋅104.
Connection
To pose an inquiry, print "? t I j x" (t=1 or t=2, 1≤i,j≤n, i≠j, 1≤x≤n−1) Then, you should peruse the appropriate response.
In the event that we reply with −1 rather than a substantial reply, that implies you surpassed the number of inquiries or made an invalid question. Exit following getting −1 and you will see the Wrong Answer decision. If not, you can get a discretionary decision in light of the fact that your answer will keep on perusing from a shut stream.
Step by step
Solved in 3 steps with 1 images
