_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 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.
Note 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.
The hidden permutation does not depend on your queries.
## Input
The first line contains single integer _n_ (1 ≤ _n_ ≤ 5000) — the length of the hidden permutation. You should read this integer first.
## Output
When your program is ready to print the answer, print three lines.
In the first line print "_!_".
In the second line print single integer _answers___cnt_ — the number of permutations indistinguishable from the hidden one, including the hidden one.
In 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.
Your program should terminate after printing the answer.
[samples]
## Interaction
To 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.
After printing the query your program should read single integer — the value of .
For 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_".
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 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.
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 line break):
* _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_
_p_0 _p_1 ... _p__n_ - 1
Contestant programs will not be able to see this input.
## Note
_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).
In 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.
The answers for the queries are:
* ,
* ,
* ,
* ,
* ,
* .
In 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.
_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 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.
Note 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.
The hidden permutation does not depend on your queries.
The first line contains single integer $n$ ($1 ≤ n ≤ 5000$) — the length of the hidden permutation. You should read this integer first.
When your program is ready to print the answer, print three lines.
In the first line print "_!_".
In the second line print single integer $answers_cnt$ — the number of permutations indistinguishable from the hidden one, including the hidden one.
In 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.
Your program should terminate after printing the answer.
To 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.
After printing the query your program should read single integer — the value of $p_i \oplus b_j$.
For 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_".
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 $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.
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 line break):
*Hacking*
For hacking use the following format:
$n$
$p_0$ $p_1$ ... $p_{n - 1}$
Contestant programs will not be able to see this input.
_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.
In 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.
The answers for the queries are:
In 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.
## Input
The first line contains single integer $n$ ($1 ≤ n ≤ 5000$) — the length of the hidden permutation. You should read this integer first.
## Output
When your program is ready to print the answer, print three lines.
In the first line print "_!_".
In the second line print single integer $answers_cnt$ — the number of permutations indistinguishable from the hidden one, including the hidden one.
In 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.
Your program should terminate after printing the answer.
[samples]
## Interaction
To 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.
After printing the query your program should read single integer — the value of $p_i \oplus b_j$.
For 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_".
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 $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.
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 line break):
*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$
$p_0$ $p_1$ ... $p_{n - 1}$
Contestant programs will not be able to see this input.
## Note
_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.
In 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.
The answers for the queries are: $p_0 \oplus b_0 = 0$, $p_1 \oplus b_1 = 0$, $p_1 \oplus b_2 = 3$, $p_0 \oplus b_2 = 2$, $p_2 \oplus b_1 = 3$, $p_2 \oplus b_0 = 2$.
In 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.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 5000 $.
Let $ p = (p_0, p_1, \dots, p_{n-1}) $ be a permutation of $ \{0, 1, \dots, n-1\} $.
Let $ b = (b_0, b_1, \dots, b_{n-1}) $ be its inverse permutation, i.e., $ b_{p_i} = i $ for all $ i \in \{0, \dots, n-1\} $, or equivalently $ p_{b_j} = j $.
**Given/Constraints**
- The hidden permutation $ p $ is fixed and unknown.
- You may query $ p_i \oplus b_j $ for any $ i, j \in \{0, \dots, n-1\} $, and receive the integer result.
- You are limited to at most $ 2n $ queries.
- After queries, you must output:
1. The number $ c $ of permutations $ p' $ consistent with all observed query results.
2. One such permutation $ p' $ consistent with the queries.
**Objective**
Compute $ c $ and output one permutation $ p' $ such that for all queried pairs $ (i,j) $,
$$
p_i \oplus b_j = p'_i \oplus b'_j
$$
where $ b' $ is the inverse of $ p' $.
The set of all such $ p' $ must include the true hidden permutation.