CF870D.Something with XOR 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 , 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.

这是一个交互式问题。

评测组隐藏了一个由 $0$ 到 $n-1$ 的整数组成的排列 $p$。你仅知道其长度 $n$。注意：在排列中，所有整数互不相同。

令 $b$ 为 $p$ 的逆排列，即对所有 $i$ 满足 $p_{b_i} = i$。你唯一能进行的操作是查询 $p_i$ 与 $b_j$ 的异或值，方法是输出两个下标 $i$ 和 $j$（二者不一定不同）。对于以 $i$ 和 $j$ 为参数的查询，你将得到值
，
其中 表示异或运算。异或运算的定义见“注意事项”部分。

注意：即使你执行全部 $n^2$ 种可能的查询，某些排列仍可能与隐藏排列无法区分。你需要计算出所有与隐藏排列无法区分的排列的个数，并输出其中任意一个这样的排列，且所用查询次数不得超过 $2n$ 次。

隐藏排列不依赖于你的查询。

The first line contains single integer n (1 ≤ n ≤ 5000) — the length of the hidden permutation. You should read this integer first.

第一行包含一个整数 $n$（$1 ≤ n ≤ 5000$）—— 表示隐藏排列的长度。你需要首先读入该整数。

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.

当你的程序准备输出答案时，请输出三行。

第一行输出 !。

第二行输出一个整数 _answers_cnt_ —— 即与隐藏排列不可区分的排列个数（包含隐藏排列本身）。

第三行输出 n 个整数 _p_0, _p_1, ..., _p_{n-1}（其中 0 ≤ _p_i < n，且所有 _p_i 互不相同）—— 即一个与隐藏排列不可区分的排列。

你的程序应在输出答案后终止。

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 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.

异或运算（XOR），即按位异或，是对两个整数执行的一种运算：其结果的二进制表示中第 $i$ 位为 $1$ 当且仅当这两个整数中恰好有一个的二进制表示的第 $i$ 位为 $1$。更多信息请参见此处。

在第一个例子中，$p = [0,\,1,\,2]$，因此 $b = [0,\,1,\,2]$，对给定的 $i,\,j$，值 均正确。不存在其他排列能对所给查询给出相同的答案。

各查询的答案为：

• ,
• ,
• ,
• ,
• ,
• .

在第二个例子中，$p = [3,\,1,\,2,\,0]$，且 $b = [3,\,1,\,2,\,0]$，对所有数对 $i,\,j$，值 均匹配。但还存在另一个满足条件的排列 $p = [0,\,2,\,1,\,3]$，对应 $b = [0,\,2,\,1,\,3]$，它同样满足全部 $n^2$ 个可能的查询。其余所有排列甚至无法满足题目中已列出的查询。