{"raw_statement":[{"iden":"problem statement","content":"This problem is **interactive**, and the **judge is adaptive**. See the notes for details.  \n**Also, the parameters in the problem statement are fixed at $N=1000$, $M=10$, $Q=950$.**\nThere are $N$ coins numbered $1, 2, \\dots, N$.  \nExactly $M$ of these coins are counterfeit.\nAn appraiser can, in one appraisal, determine whether two coins are of the same type or different types. Specifically:\n\n*   If the two coins are both genuine or both counterfeit, they are judged to be of the same type.\n*   Otherwise, they are judged to be of different types.\n\nIdentify all the counterfeit coins using at most $Q$ appraisals."},{"iden":"constraints","content":"*   $\\color{red}{N = 1000}$\n*   $\\color{red}{M = 10}$\n*   $\\color{red}{Q = 950}$"},{"iden":"interaction","content":"This is an interactive problem.  \nInitially, receive $N$, $M$, and $Q$ from Standard Input:\n\n$N$ $M$ $Q$\n\n  \n\nNext, you can perform appraisals between $0$ and $Q$ times, inclusive, as follows.\nFirst, by outputting to Standard Output in the following format, you indicate that you are appraising coins $x$ and $y$. (Include a newline at the end.)\n\n? $x$ $y$\n\nHere, $x$ and $y$ must be distinct integers between $1$ and $N$, inclusive.\nIn response, the judge system will reply with one of the following three responses.\n\n0\n\nIf the response is `0`, it means that coins $x$ and $y$ are of the same type.\n\n1\n\nIf the response is `1`, it means that coins $x$ and $y$ are of different types.\n\n\\-1\n\nIf the response is `-1`, it means that the appraisal is invalid. Specifically, this response is given when at least one of the following conditions is met:\n\n*   The outputted $x$ and $y$ does not satisfy the constraints.\n*   The number of appraisals exceeds $Q$.\n\nIf you receive this response, your program is considered incorrect. Terminate your program immediately.\n  \n\nFinally, by outputting to Standard Output in the following format, you answer that coins $A_1, A_2, \\dots, A_{M}$ are counterfeit. (Include a newline at the end.)\n\n! $A_1$ $A_2$ $\\dots$ $A_{M}$\n\nHere, $A_i$ must be distinct integers between $1$ and $N$, inclusive.  \nAfter this output, terminate your program immediately.\nIf any of your outputs do not meet the specified format, your program will be considered incorrect. The judge will then respond with `-1`, so in that case, terminate your program immediately."},{"iden":"notes","content":"*   **Every time you output, include a newline at the end and flush Standard Output.** Failure to do so may result in a verdict of TLE or WA.\n*   After outputting your answer (or receiving `-1`), terminate your program immediately. Otherwise, the verdict is indeterminate.\n*   Beware that unnecessary newlines are considered as malformed.\n*   **The judge for this problem is adaptive.** That is, at any point, as long as consistency can be maintained, the judge may change which coins are counterfeit. See the sample interaction for details."},{"iden":"sample interaction","content":"In this interaction, $N=5$, $M=2$, $Q=10$, and the judge initially considers coins $1$ and $2$ to be counterfeit.\nNote that this example does not meet the constraints and is not included in the judge.\n\nInput　\n\nOutput\n\nExplanation\n\n`5 2 10`\n\n$N$, $M$, and $Q$ are given.\n\n`? 1 2`\n\nYou appraise coins $1$ and $2$.\n\n`0`\n\nCoins $1$ and $2$ are judged to be of the same type.\n\n`? 1 3`\n\nYou appraise coins $1$ and $3$.\n\n`1`\n\nCoins $1$ and $3$ are judged to be of different types.\n\n`? 1 4`\n\nYou appraise coins $1$ and $4$.\n\n`1`\n\nCoins $1$ and $4$ are judged to be of different types.\n\n`! 1 2`\n\nYou answer that coins $1$ and $2$ are counterfeit.\n\nIndeed, coins $1$ and $2$ are considered counterfeit, but it is also possible to consider coins $3$ and $4$ as counterfeit while maintaining consistency.  \nTherefore, the judge may change the counterfeit coins to $3$ and $4$.  \nAs a result, the judge may judge this answer as incorrect."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}