The penguin's game
Contest: Codeforces Round 427 (Div. 2)
Difficulty rating: 2400
Tags: binary search, constructive algorithms, interactive

Pay attention: this problem is interactive.

Penguin Xoriy came up with a new game recently. He has n icicles numbered from 1 to n. Each icicle has a temperature — an integer from 1 to 109. Exactly two of these icicles are special: their temperature is y, while a temperature of all the others is x ≠ y. You have to find those special icicles. You can choose a non-empty subset of icicles and ask the penguin what is the bitwise exclusive OR (XOR) of the temperatures of the icicles in this subset. Note that you can't ask more than 19 questions.

You are to find the special icicles.

Input format:
The first line contains three integers n, x, y (2 ≤ n ≤ 1000, 1 ≤ x, y ≤ 109, x ≠ y) — the number of icicles, the temperature of non-special icicles and the temperature of the special icicles.

Output format:
To give your answer to the penguin you have to print character "!" (without quotes), then print two integers p1, p2 (p1 < p2) — the indexes of the special icicles in ascending order. Note that "!" and p1 should be separated by a space; the indexes should be separated by a space too. After you gave the answer your program should terminate immediately.

Interaction format:
To ask a question print character "?" (without quotes), an integer c (1 ≤ c ≤ n), and c distinct integers p1, p2, ..., pc (1 ≤ pi ≤ n) — the indexes of icicles that you want to know about. Note that "?" and c should be separated by a space; the indexes should be separated by a space too.

After you asked the question, read a single integer — the answer.

Note that you can't ask more than 19 questions. If you ask more than 19 questions or at least one incorrect question, your solution will get "Wrong answer".

If at some moment your program reads  - 1 as an answer, it should immediately exit (for example, by calling exit(0)). You will get "Wrong answer" in this case, it means that you asked more than 19 questions, or asked an invalid question. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Your solution will get "Idleness Limit Exceeded", if you don't print anything or forget to flush the output, including for the final answer .

To flush you can use (just after printing):

- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- For other languages see the documentation.

Hacking

For hacking use the following format:

n x y p1 p2

Here 1 ≤ p1 < p2 ≤ n are the indexes of the special icicles.

Contestant programs will not be able to see this input.

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

Note:
The answer for the first question is $$1 \oplus 2 \oplus 1 = 2$$.

The answer for the second and the third questions is 1, therefore, special icicles are indexes 1 and 3.

You can read more about bitwise XOR operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.

Example input:
4 2 1
2
1
1

Example output:
? 3 1 2 3
? 1 1
? 1 3
! 1 3

Editorial:
The solution can be separated into several parts.
I. Finding the parity of the number of special icicles in the given subset using 1 question.
Consider the following cases:
1. Subset's size is even, the number of special icicles in it is even. Then the answer to such question is 0.
2. Subset's size is even, the number of special icicles in it is odd. Then the answer to such question is $$x \oplus y$$.
3. Subset's size is odd, the number of special icicles in it is even. Then the answer to such question is x.
4. Subset's size is odd, the number of special icicles in it is odd. Then the answer to such question is y.
x, y ≥ 1 and x ≠ y, so the numbers 0, x, y, $$x \oplus y$$ are pairwise distinct. Therefore, we can find the parity of the number of special icicles on the given subset using 1 question.
II. The solution for the problem for the only one special icicle.
Suppose we have n icicles, and one of them is special. Then you can find it using $$\left\lceil \log _ { 2 } n \right\rceil$$ questions.
The algorithm is to use binary search over the minimum prefix that contains the special icicle.
III. The solution of our problem.
Each integer n ≤ 1000 can be written using no more than $$\left\lfloor \log_{2} n \right\rfloor + 1$$ bits. Iterate over the bits from 0 to $$\left\lfloor \log_{2} n \right\rfloor$$. Ask a question about the icicles that have 1 in their numbers in the fixed bit. After that, we can determine if the numbers of the special icicles differ in this bit. Really, the bits differ if this subset's size is odd, and don't differ otherwise.
Obviously, we will find at least one bit, where their numbers differ. Let A is the subset of the icicles that have 1 in this bit, and B is the complement set. Let m is the size of the smallest from these subsets. Then $$m \leq \frac{n}{2}$$. Let's solve the problem for the only one special icicle for the smallest of these subsets.
Then it's easy to get the number of the other icicle: we know the number of the first icicle and we know in which bits the numbers differ and in which don't.
This solution uses 19 question. It can be proven that in the given constraints you can't solve this problem in less than 19 questions.