write a go solution for D1. Diadrash (Easy Version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output This is the Easy version of the problem. The difference between the versions is that in this version, you can make at most max(300,ceil(n/2)+2) queries. You can hack only if you solved all versions of this problem. This problem is interactive.There is a permutation^∗ p of the integers from 0 to n-1 hidden from you. Additionally, you are given q ranges [l_1,r_1],[l_2,r_2],ldots,[l_q,r_q] where 1<=l_i<=r_i<=n.You need to discover the maximum operatornameMEX among the values of p in the q ranges that are given to you in the input. Formally, you must discover the value of max_i=1^qoperatornameMEX([p_l_i,p_l_i+1,ldots,p_r_i])^†. To do this, you may make at most max(300,ceil(n/2)+2) queries of the following form:  Choose any two integers 1<=l<=r<=n and you will receive the value operatornameMEX([p_l,p_l+1,ldots,p_r]). ^∗A permutation of the integers from 0 to n-1 is a sequence of n elements where every integer from 0 to n-1 appears exactly once. For example, the sequence [0,3,1,2] is a permutation, but the sequence [0,0,2,1] is not.^†The operatornameMEX of a sequence is defined as the smallest non-negative integer that does not appear in that sequence. For example, operatornameMEX([0,0,1,3])=2 and operatornameMEX([1,2,2])=0.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=100). The description of the test cases follows. The first line of each test case contains exactly two integers n and q (4<=n<=10^4, 1<=q<=3*10^5) — the size of the permutation and the number of ranges, respectively.The i-th of the next q lines contains two integers l_i,r_i (1<=l_i<=r_i<=n).It is guaranteed that the sum of n and q do not exceed 10^4 and 3*10^5 respectively over all test cases.Additional Constraint: it is guaranteed that no range is repeated in the same test case.InteractionTo ask a query, output a line in the following format (without the quotes):  "? l r" (1<=l<=r<=n) The jury will return a single integer, the value of operatornameMEX([p_l,p_l+1,ldots,p_r]).When you have found the answer, output a single line in the following format:  "! x" (0<=x<=n). After that, proceed to process the next test case or terminate the program if it was the last test case. Printing the answer does not count as a query.The interactor is not adaptive, meaning that the values of the permutation are known before the participant asks the queries.If your program makes more than max(300,ceil(n/2)+2) queries, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.After printing a query do not forget to output the end of line and flush the output. Otherwise, you may get the Idleness Limit Exceeded verdict. To do this, use:  fflush(stdout) or cout.flush() in C++  System.out.flush() in Java;  flush(output) in Pascal;  stdout.flush() in Python;  see the documentation for other languages. HacksFor hacks, use the following format.The first line of the input should contain a single integer t (1<=t<=100) — the number of test cases.The first line of each test case should contain exactly two integers n and q (4<=n<=10^4, 1<=q<=3*10^5) — the size of the permutation and the number of ranges you are given, respectively.The second line should contain n integers p_1,p_2,ldots,p_n — where p_i is the i-th element of the permutation. It should hold that p is a permutation containing integers 0 to n-1.The i-th of the next q lines should contain two integers l_i, r_i (1<=l_i<=r_i<=n).It should hold that the sum of n and q do not exceed 10^4 and 3*10^5 respectively over all test cases.Additional Constraint: no range should be repeated in the same test case.ExampleInput3
4 3
1 2
2 4
1 3

2

0

1

4

6 6
1 2
2 4
3 3
4 6
5 5
6 6

6

1

2

4 4
1 1
2 2
3 3
4 4

Output





? 1 3

? 4 4

? 1 1

? 1 4

! 2







? 1 6

? 3 3

? 2 4

! 2





! 1NoteIn the first example, the hidden permutation is p=[0,3,1,2] and the ranges are [1,2],[2,4],[1,3]. The third range is optimal, as operatornameMEX([p_1,p_2,p_3])=operatornameMEX([0,3,1])=2, which is maximum.In our first query, we ask about l=1,r=3 and the judge gives us the value operatornameMEX([p_1,p_2,p_3])=2. In the second query, we ask about l=4,r=4 and the judge gives us the value operatornameMEX([p_4])=0. Likewise, operatornameMEX([p_1])=1 and operatornameMEX([p_1,p_2,p_3,p_4])=4.Somehow, we figure out that the answer we are looking for is 2.In the second example, p=[3,5,0,1,4,2].In the third example, p=[0,1,2,3].Note that this is just an explanation of the way the interaction works and does not show any strategy to solve the problem.. Output only the code with no comments, explanation, or additional text.