Joking (Hard Version)
Contest: Codeforces Global Round 23
Difficulty rating: 3200
Tags: dp, interactive

The only difference between this problem and the hard version is the maximum number of questions.

This is an interactive problem.

There is a hidden integer $$$1 \le x \le n$$$ which you have to find. In order to find it you can ask at most $$$\mathbf{53}$$$ questions.

In each question you can choose a non-empty integer set $$$S$$$ and ask if $$$x$$$ belongs to $$$S$$$ or not, after each question, if $$$x$$$ belongs to $$$S$$$, you'll receive "YES", otherwise "NO".

But the problem is that not all answers are necessarily true (some of them are joking), it's just guaranteed that for each two consecutive questions, at least one of them is answered correctly.

Additionally to the questions, you can make at most $$$2$$$ guesses for the answer $$$x$$$. Each time you make a guess, if you guess $$$x$$$ correctly, you receive ":)" and your program should terminate, otherwise you'll receive ":(".

As a part of the joking, we will not fix the value of $$$x$$$ in the beginning. Instead, it can change throughout the interaction as long as all the previous responses are valid as described above.

Note that your answer guesses are always answered correctly. If you ask a question before and after a guess, at least one of these two questions is answered correctly, as normal.

Input format:
The only line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the maximum possible value of $$$x$$$.

Interaction format:
For each question, if you want to ask about a set $$$S$$$, first print the character '?', then print the size of $$$S$$$ and then print the elements of $$$S$$$ one by one. Each element should be an integer between $$$1$$$ and $$$n$$$, the elements must be distinct. After each question, read a string "YES" or "NO", as explained in the statement. You can make at most $$$53$$$ such questions.

If you want to guess for $$$x$$$, first print the character '!' and then print your guess. After each guess, read ":)" or ":(". If you guess $$$x$$$ correctly, the answer is ":)" and your program should terminate immediately, otherwise you'll receive ":(". You can make at most $$$2$$$ such guesses.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. 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 documentation for other languages.

Hacking is not allowed in this problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
If the answer of the first question were correct, then $$$x$$$ would have been equal to $$$6$$$, but as we can see in the first guess, $$$6$$$ is not the answer.

So the answer of the first question is joking. As we know, the answer of at least one of our two questions is correct, since the answer of the first question was joking, the answer of the second question should be correct.

So we will understand that $$$x$$$ is not equal to $$$1, 2, 3$$$ or $$$4$$$, and we also knew that $$$x$$$ is not equal to $$$6$$$ either. Hence $$$x$$$ should be equal to $$$5$$$.

Example input:
6
NO
:(
NO
:)

Example output:
? 5 1 2 5 4 3
! 6
? 4 1 2 3 4
! 5

Editorial:
Step 1:
First note that in any question we ask, a set will be introduced as the set that contains $$$x$$$. If the answer is "YES", then the set that we asked is introduced and otherwise, its complement.
Task: Assume that our current search domain is some set $$$V$$$. In addition, assume that $$$V = A \cup B$$$ such that set $$$A$$$ is the set that introduced to contain $$$x$$$ in very last step and $$$B$$$ is the set of other candidates for $$$x$$$ (candidates that don't belong to $$$A$$$). Now assume that in next question, a set $$$C$$$ is introduced to contain $$$x$$$ such that $$$C = a \cup b, (a \in A , b \in B)$$$. what can we do? how can we reduce our search domain after this question?
Solution: Considering the solution of E1, it's not so hard to see that we can remove $$$B-b$$$ from our search domain. So our new search domain will be $$$V' = A' \cup B'$$$ such that $$$A' = C = a \cup b$$$ is the set of candidates that introduced in last question and $$$B' = A - a$$$ is the set of other candidates.
Step 2:
Task: Let's calculate minimum needed questions for a search domain of size $$$n$$$ using the idea of previous step.
Solution: We can do it using a simple dp, let $$$dp[A][B]$$$ be the minimum number of questions needed to find $$$x$$$ in a search domain of size $$$A+B$$$ in which $$$A$$$ numbers are introduced in last question and $$$B$$$ numbers are not. In order to calculate our dp, if we ask about some set which consists of $$$a$$$ numbers from first set and $$$b$$$ numbers from second set, we should update $$$dp[A][B]$$$ from $$$dp[A-a][a+b]$$$. So we can say that: $$$$$$dp[A][B] = \min_{a \le A , b \le B} dp[A-a][a+b]$$$$$$. Using this dp and keeping track of its updates, we can simply solve the task. But there is a problem, we don't have enough time to calculate the whole dp. So what can we do?
Step 3:
Task: Since calculating $$$dp[A][B]$$$ for $$$A <= n , B <= m$$$ is $$$O(n^2 \cdot m^2)$$$, we can only calculate it for small $$$n$$$ and $$$m$$$ like $$$n,m \le 100$$$. What can we do for the rest? Maybe some heuristic method?
Solution: It's not so hard to see that for most $$$A$$$ and $$$B$$$ (especially for large values) it's best to update $$$dp[A][B]$$$ from something around $$$dp[A-A/2][A/2+B/2]$$$ (in other words, asking $$$A/2$$$ numbers from the first set and $$$B/2$$$ numbers from the second one). Using such method, we can calculate dp in a reasonable time and with a very good accuracy, and this accuracy is enough to find the answer in less than $$$53$$$ (even less) questions.