Joking (Easy Version)
Contest: Codeforces Global Round 23
Difficulty rating: 2500
Tags: binary search, constructive algorithms, interactive, ternary search

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{82}$$$ 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 $$$82$$$ 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:
Task: How can we make sure that some statement is not joking? Solution: If something is told for two times in a row, we can be sure that it's true. For example if we are told that $$$x \ne 3$$$ in two consecutive questions, we can be sure that it's true. Because at least one of those questions is answered correctly and that's enough.
Step 2:
Task: What can be found out if we ask about a set $$$S$$$? (assume that we will be answered correctly) Solution: If the answer is "YES", then $$$x \in S$$$ and we can reduce our search domain to $$$S$$$. Otherwise, we can remove $$$S$$$ from the search domain.
Step 3:
Task: Using previous steps, how can we really reduce our search domain? Step 2 can do it only if we have a correct statement about $$$x$$$ and using Step 1, we can find something that is surely correct. Solution: Assume that $$$V$$$ is our current search domain. Split it into $$$4$$$ subsets $$$V_{1}, V_{2}, V_{3}$$$ and $$$V_{4}$$$. then ask about following sets:
• $$$V_{1} \cup V_{2}$$$
• $$$V_{1} \cup V_{3}$$$
So after these questions, we can reduce size of search domain by at least $$$min(|V_{1}|,|V_{2}|,|V_{3}|,|V_{4}|)$$$, and it's obvious to see that we can choose $$$V_{i}$$$'s in such a way that this value is at least $$$\frac{|V|}{4}$$$.
Finally, as long as size of the search domain is greater than $$$3$$$, we can reduce it using this algorithm. It can be shown easily that we can reduce our search domain to only $$$3$$$ numbers with at most $$$76$$$ questions.
Step 4:
Task: Now assume that we have only $$$3$$$ candidates for $$$x$$$, since we have only $$$2$$$ chances to guess, we must remove one of them. How can we do it? Note that since we've used $$$76$$$ questions in previous step, we only have $$$6$$$ questions left.
Solution: Assume that our three candidates are $$$a, b$$$ and $$$c$$$. it can be shown that using following questions, we can always remove at least one of them from the search domain:
• $$$\{a\}$$$
• $$$\{b\}$$$
• $$$\{b\}$$$
• $$$\{a\}$$$
After that, when we have only two candidates for $$$x$$$, we can guess them one by one and we are done.