write a go solution for E2. Hidden Single (Version 2)time limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAdhesiveWombat - Overdrive⠀The two versions have different constraints on t, n, and the maximum number of queries, and solving one of the two versions does not necessarily solve the other. You may want to read both versions. Hacks are disabled in both versions.This is an interactive problem.There is a hidden array a_1,a_2,ldots,a_2n-1 containing all the numbers from 1 to n, and all of them appear twice except one (which only appears once).You can ask queries in the following format, where S is a subset of 1,2,ldots,2n-1 and x is an integer in [1,n]: textttask(S,x): does there exist iinS such that a_i=x? Find the number appearing exactly once, using at most 925 queries. You don't need to find its position.Note that the interactor is not adaptive, which means that the hidden array does not depend on the queries you make.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=20). The description of the test cases follows. The first line of each test case contains a single integer n (n=300) — the maximum value in the hidden array a_1,a_2,ldots,a_2n-1.There are exactly 50 tests in this problem (including the example). The example has t=1, and all the other tests have t=20.InteractionFor each test case, first read a single integer n. If the integer you read is -1, it means that the answer to the previous test case was wrong, and you should exit immediately. You may ask up to 925 queries in each test case.To ask a query, print a line in the format texttt?x|S|S_1S_2...S_|S| with 1<=x<=n, 1<=S_1,S_2,ldots,S_|S|<=2n-1, and all the S_i distinct.As a response to the query, you will get 1 if the answer is yes, 0 if the answer is no, and -1 if you made an invalid query. You should exit immediately if you receive a -1.To output an answer, you should print texttt!y, where y is the number that appears exactly once. Printing the answer doesn't count as a query.See the interaction example for more clarity.If you ask too many queries, you ask a malformed query, or your answer is wrong, you will get textttWronganswer.After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get textttIdlenesslimitexceeded. To do this, use: textttfflush(stdout) or textttcout.flush() in C++; textttSystem.out.flush() in Java; textttflush(output) in Pascal; textttstdout.flush() in Python; see the documentation for other languages. Note that the interactor is not adaptive, which means that the hidden arrays do not depend on the queries you make.ExampleInput1 300 0 Output ? 187 1 1 ! 187NoteIn the first test case, n=300, so the hidden array has length 2n-1=599. #Contestant printsInteractor repliesExplanation1? 187 1 10Query: does a_1=187? No.2! 187We feel lucky, and claim that the answer is 187. Fortunately, the answer is correct. We have asked 1 query (printing the answer does not count as a query), which is less than the maximum allowed number of queries (925).. Output only the code with no comments, explanation, or additional text.