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 <= j <= i -1)$ such that $b_i plus.circle p_j = 0$.
You need to minimize $\\sum_{i = 2}^{n} p o p c o u n t (a [ p [ i ] ] plus.circle a [ b [ i ] ])$, where $p o p c o u n t (x)$ represents the number of $1$ in the binary representation of $x$, $plus.circle$ means bitwise exclusive OR operation.
The input consists of multiple test cases.
The first line contains an integer $T$ $(1 <= T <= 10)$ — the number of test cases. The description of the test cases follows.
The first line contains one integers $n$ $(1 <= n <= 2 * 10^5)$ .
The second line contains $n$ distinct integers $a_1, a_2, \\dots, a_n (0 <= 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.
If there are several answers, you can print any.
## Input
The input consists of multiple test cases. The first line contains an integer $T$ $(1 <= T <= 10)$ — the number of test cases. The description of the test cases follows.The first line contains one integers $n$ $(1 <= n <= 2 * 10^5)$ .The second line contains $n$ distinct integers $a_1, a_2, \\dots, a_n (0 <= a_i < 2^(18))$ .
## Output
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.If there are several answers, you can print any.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ a, b \in \mathbb{Z}^+ $ be given parameters.
**Curves**
The closed region is bounded by:
1. $ y_1(x) = \sqrt{a^2 - (x - a)^2} $ — upper semicircle centered at $ (a, 0) $
2. $ y_2(x) = \sqrt{a^2 - (x + a)^2} $ — upper semicircle centered at $ (-a, 0) $
3. $ y_3(x) = \frac{2b}{\pi} \left( \arccos\left(\frac{x + a}{a}\right) - \pi \right) $
4. $ y_4(x) = \frac{2b}{\pi} \left( \arcsin\left(\frac{x - a}{a}\right) - \frac{\pi}{2} \right) $
**Constraints**
- $ 1 \leq T \leq 1000 $
- $ 1 \leq a, b \leq 1000 $
**Objective**
Compute the area $ A $ of the region enclosed by the four curves.
The region is symmetric and consists of two semicircular caps of radius $ a $ and two symmetric curved sides defined by inverse trigonometric functions. The total area is the sum of:
- Area of two semicircles: $ \frac{1}{2} \pi a^2 \times 2 = \pi a^2 $
- Area between the two inverse-trig curves from $ x = -a $ to $ x = a $, which evaluates to $ 2ab $
Thus:
$$
A = \pi a^2 + 2ab
$$