Codeforces Round 427 (Div. 2)
E
The penguin's game
Codeforces
2400
原题
← DF →
翻译中…

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 $10^{9}$. 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

翻译中…

The first line contains three integers $*n*$, $*x*$, $*y*$ ($2 ≤ *n* ≤ 1000$, $1 ≤ *x*, *y* ≤ 10^{9}$, $*x* ≠ *y*$) — the number of icicles, the temperature of non-special icicles and the temperature of the special icicles.

翻译中…

Output

翻译中…

To give your answer to the penguin you have to print character "!" (without quotes), then print two integers $*p*_{1}$, $*p*_{2}$ ($*p*_{1} < *p*_{2}$) — the indexes of the special icicles in ascending order. Note that "!" and $*p*_{1}$ 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

翻译中…

To ask a question print character "?" (without quotes), an integer $*c*$ ($1 ≤ *c* ≤ *n*$), and $*c*$ distinct integers $*p*_{1}$, $*p*_{2}$, ..., $*p*_{*c*}$ ($1 ≤ *p*_{*i*} ≤ *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*$ $*p*_{1}$ $*p*_{2}$

翻译中…

Here $1 ≤ *p*_{1} < *p*_{2} ≤ *n*$ are the indexes of the special icicles.

翻译中…

Contestant programs will not be able to see this input.

翻译中…

Note

翻译中…

The answer for the first question is image.

翻译中…

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.

翻译中…

样例

Input #1
4 2 1
2
1
1
Output #1
? 3 1 2 3
? 1 1
? 1 3
! 1 3
InputCopy OutputCopy
题目信息
题号
835E
时间限制
1 s
内存限制
256 MB
标签
二分
构造
交互题

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。