{"problem":{"name":"D. Something with XOR Queries","description":{"content":"_This is an interactive problem._ Jury has hidden a permutation _p_ of integers from 0 to _n_ - 1. You know only the length _n_. Remind that in permutation all integers are distinct. Let _b_ be the ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF872D"},"statements":[{"statement_type":"Markdown","content":"_This is an interactive problem._\n\nJury has hidden a permutation _p_ of integers from 0 to _n_ - 1. You know only the length _n_. Remind that in permutation all integers are distinct.\n\nLet _b_ be the inverse permutation for _p_, i.e. _p__b__i_ = _i_ for all _i_. The only thing you can do is to ask _xor_ of elements _p__i_ and _b__j_, printing two indices _i_ and _j_ (not necessarily distinct). As a result of the query with indices _i_ and _j_ you'll get the value , where denotes the _xor_ operation. You can find the description of _xor_ operation in notes.\n\nNote that some permutations can remain indistinguishable from the hidden one, even if you make all possible _n_2 queries. You have to compute the number of permutations indistinguishable from the hidden one, and print one of such permutations, making no more than 2_n_ queries.\n\nThe hidden permutation does not depend on your queries.\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 5000) — the length of the hidden permutation. You should read this integer first.\n\n## Output\n\nWhen your program is ready to print the answer, print three lines.\n\nIn the first line print \"_!_\".\n\nIn the second line print single integer _answers___cnt_ — the number of permutations indistinguishable from the hidden one, including the hidden one.\n\nIn the third line print _n_ integers _p_0, _p_1, ..., _p__n_ - 1 (0 ≤ _p__i_ < _n_, all _p__i_ should be distinct) — one of the permutations indistinguishable from the hidden one.\n\nYour program should terminate after printing the answer.\n\n[samples]\n\n## Interaction\n\nTo ask about _xor_ of two elements, print a string \"_? i j_\", where _i_ and _j_ — are integers from 0 to _n_ - 1 — the index of the permutation element and the index of the inverse permutation element you want to know the _xor_\\-sum for. After that print a line break and make _flush_ operation.\n\nAfter printing the query your program should read single integer — the value of .\n\nFor a permutation of length _n_ your program should make no more than 2_n_ queries about _xor_\\-sum. Note that printing answer doesn't count as a query. Note that you can't ask more than 2_n_ questions. If you ask more than 2_n_ questions or at least one incorrect question, your solution will get \"_Wrong answer_\".\n\nIf 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 2_n_ 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.\n\nYour solution will get \"_Idleness Limit Exceeded_\", if you don't print anything or forget to flush the output, including for the final answer .\n\nTo flush you can use (just after printing line break):\n\n*   _fflush(stdout)_ in C++;\n*   _System.out.flush()_ in Java;\n*   _stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   For other languages see the documentation.\n\n**Hacking**\n\nFor hacking use the following format:\n\n_n_\n\n_p_0 _p_1 ... _p__n_ - 1\n\nContestant programs will not be able to see this input.\n\n## Note\n\n_xor_ operation, or bitwise exclusive OR, is an operation performed over two integers, in which the _i_\\-th digit in binary representation of the result is equal to 1 if and only if exactly one of the two integers has the _i_\\-th digit in binary representation equal to 1. For more information, see [here](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).\n\nIn the first example _p_ = \\[0, 1, 2\\], thus _b_ = \\[0, 1, 2\\], the values are correct for the given _i_, _j_. There are no other permutations that give the same answers for the given queries.\n\nThe answers for the queries are:\n\n*   ,\n*   ,\n*   ,\n*   ,\n*   ,\n*   .\n\nIn the second example _p_ = \\[3, 1, 2, 0\\], and _b_ = \\[3, 1, 2, 0\\], the values match for all pairs _i_, _j_. But there is one more suitable permutation _p_ = \\[0, 2, 1, 3\\], _b_ = \\[0, 2, 1, 3\\] that matches all _n_2 possible queries as well. All other permutations do not match even the shown queries.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"_This is an interactive problem._\n\nJury has hidden a permutation $p$ of integers from $0$ to $n - 1$. You know only the length $n$. Remind that in permutation all integers are distinct.\n\nLet $b$ be the inverse permutation for $p$, i.e. $p_{b_i} = i$ for all $i$. The only thing you can do is to ask _xor_ of elements $p_i$ and $b_j$, printing two indices $i$ and $j$ (not necessarily distinct). As a result of the query with indices $i$ and $j$ you'll get the value $p_i \\oplus b_j$, where $\\oplus$ denotes the _xor_ operation. You can find the description of _xor_ operation in notes.\n\nNote that some permutations can remain indistinguishable from the hidden one, even if you make all possible $n^2$ queries. You have to compute the number of permutations indistinguishable from the hidden one, and print one of such permutations, making no more than $2n$ queries.\n\nThe hidden permutation does not depend on your queries.\n\nThe first line contains single integer $n$ ($1 ≤ n ≤ 5000$) — the length of the hidden permutation. You should read this integer first.\n\nWhen your program is ready to print the answer, print three lines.\n\nIn the first line print \"_!_\".\n\nIn the second line print single integer $answers_cnt$ — the number of permutations indistinguishable from the hidden one, including the hidden one. \n\nIn the third line print $n$ integers $p_0, p_1, ..., p_{n - 1}$ ($0 ≤ p_i < n$, all $p_i$ should be distinct) — one of the permutations indistinguishable from the hidden one.\n\nYour program should terminate after printing the answer.\n\nTo ask about _xor_ of two elements, print a string \"_? i j_\", where $i$ and $j$ — are integers from $0$ to $n - 1$ — the index of the permutation element and the index of the inverse permutation element you want to know the _xor_-sum for. After that print a line break and make _flush_ operation.\n\nAfter printing the query your program should read single integer — the value of $p_i \\oplus b_j$.\n\nFor a permutation of length $n$ your program should make no more than $2n$ queries about _xor_-sum. Note that printing answer doesn't count as a query. Note that you can't ask more than $2n$ questions. If you ask more than $2n$ questions or at least one incorrect question, your solution will get \"_Wrong answer_\".\n\nIf 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 $2n$ 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.\n\nYour solution will get \"_Idleness Limit Exceeded_\", if you don't print anything or forget to flush the output, including for the final answer .\n\nTo flush you can use (just after printing line break): \n\n*Hacking*\n\nFor hacking use the following format:\n\n$n$\n\n$p_0$ $p_1$ ... $p_{n - 1}$\n\nContestant programs will not be able to see this input.\n\n_xor_ operation, or bitwise exclusive OR, is an operation performed over two integers, in which the $i$-th digit in binary representation of the result is equal to $1$ if and only if exactly one of the two integers has the $i$-th digit in binary representation equal to $1$. For more information, see here.\n\nIn the first example $p = [0, 1, 2]$, thus $b = [0, 1, 2]$, the values $p_i \\oplus b_j$ are correct for the given $i, j$. There are no other permutations that give the same answers for the given queries.\n\nThe answers for the queries are: \n\nIn the second example $p = [3, 1, 2, 0]$, and $b = [3, 1, 2, 0]$, the values $p_i \\oplus b_j$ match for all pairs $i, j$. But there is one more suitable permutation $p = [0, 2, 1, 3]$, $b = [0, 2, 1, 3]$ that matches all $n^2$ possible queries as well. All other permutations do not match even the shown queries.\n\n## Input\n\nThe first line contains single integer $n$ ($1 ≤ n ≤ 5000$) — the length of the hidden permutation. You should read this integer first.\n\n## Output\n\nWhen your program is ready to print the answer, print three lines.\nIn the first line print \"_!_\".\nIn the second line print single integer $answers_cnt$ — the number of permutations indistinguishable from the hidden one, including the hidden one. \nIn the third line print $n$ integers $p_0, p_1, ..., p_{n - 1}$ ($0 ≤ p_i < n$, all $p_i$ should be distinct) — one of the permutations indistinguishable from the hidden one.\nYour program should terminate after printing the answer.\n\n[samples]\n\n## Interaction\n\nTo ask about _xor_ of two elements, print a string \"_? i j_\", where $i$ and $j$ — are integers from $0$ to $n - 1$ — the index of the permutation element and the index of the inverse permutation element you want to know the _xor_-sum for. After that print a line break and make _flush_ operation.\nAfter printing the query your program should read single integer — the value of $p_i \\oplus b_j$.\nFor a permutation of length $n$ your program should make no more than $2n$ queries about _xor_-sum. Note that printing answer doesn't count as a query. Note that you can't ask more than $2n$ questions. If you ask more than $2n$ questions or at least one incorrect question, your solution will get \"_Wrong answer_\".\nIf 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 $2n$ 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.\nYour solution will get \"_Idleness Limit Exceeded_\", if you don't print anything or forget to flush the output, including for the final answer .\nTo flush you can use (just after printing line break): \n\n*Hacking*\n\nFor hacking use the following format:\n\n$n$\n\n$p_0$ $p_1$ ... $p_{n - 1}$\n\nContestant programs will not be able to see this input.\n\n## Note\n\n_xor_ operation, or bitwise exclusive OR, is an operation performed over two integers, in which the $i$-th digit in binary representation of the result is equal to $1$ if and only if exactly one of the two integers has the $i$-th digit in binary representation equal to $1$. For more information, see here.\n\nIn the first example $p = [0, 1, 2]$, thus $b = [0, 1, 2]$, the values $p_i \\oplus b_j$ are correct for the given $i, j$. There are no other permutations that give the same answers for the given queries.\n\nThe answers for the queries are:  $p_0 \\oplus b_0 = 0 \\oplus 0 = 0$,  $p_1 \\oplus b_1 = 1 \\oplus 1 = 0$,  $p_1 \\oplus b_2 = 1 \\oplus 2 = 3$,  $p_0 \\oplus b_2 = 0 \\oplus 2 = 2$,  $p_2 \\oplus b_1 = 2 \\oplus 1 = 3$,  $p_2 \\oplus b_0 = 2 \\oplus 0 = 2$.\n\nIn the second example $p = [3, 1, 2, 0]$, and $b = [3, 1, 2, 0]$, the values $p_i \\oplus b_j$ match for all pairs $i, j$. But there is one more suitable permutation $p = [0, 2, 1, 3]$, $b = [0, 2, 1, 3]$ that matches all $n^2$ possible queries as well. All other permutations do not match even the shown queries.","is_translate":true,"language":"Chinese"}],"meta":{"iden":"CF872D","tags":["brute force","implementation","interactive"],"sample_group":[["3\n0\n0\n3\n2\n3\n2","? 0 0\n? 1 1\n? 1 2\n? 0 2\n? 2 1\n? 2 0\n!\n1\n0 1 2"],["4\n2\n3\n2\n0\n2\n3\n2\n0","? 0 1\n? 1 2\n? 2 3\n? 3 3\n? 3 2\n? 2 1\n? 1 0\n? 0 0\n!\n2\n3 1 2 0"]],"created_at":"2026-03-03 11:00:39"}}