Given a sequence $a$ consists $n$ distinct integers. Please construct a permutation $p$ and a sequence $b$ satisfied:
- Both $p$ and $b$ have exactly $n$ elements; - For every $i \in [2,n]$ ,there exist an indice $j(1 \leq j \leq i-1)$ such that $b_i \oplus p_j=0$.
You need to minimize $\sum\limits_{i=2}^n popcount(a[p[i]] \oplus a[b[i]])$, where $popcount(x)$ represents the number of $1$ in the binary representation of $x$, $\oplus$ means bitwise exclusive OR operation.
输入解释
The input consists of multiple test cases. The first line contains an integer $T$ $(1 \leq T \leq 10)$ — the number of test cases. The description of the test cases follows.
The first line contains one integers $n$ $(1 \leq n \leq 2*10^5)$ .
The second line contains $n$ distinct integers $a_1,a_2,\dots,a_n(0 \leq a_i < 2^{18})$ .
输出解释
For each test case, print three lines.
The first line contains one number, represents the minimum value.
The second line contains $n$ numbers $p_1,p_2,\dots,p_n$ — the permutation you construct.
The last line contains $n$ numbers $b_1,b_2,\dots,b_n$ — the sequence you construct.