Problem D
Pickle Jars

There are $N$ jars of pickles on your shelf, and you would like to put all pickles into a single jar.

You can first reorder the jars of pickles in any order you want. To transfer pickles, you first choose two adjacent jars. Then, you move all pickles from the left jar to the right jar, and finally remove the left jar. You will continue transfering pickles until there is only one single jar remaining.

You can freely change the initial order of jars and how to combine them. Depending on how this process is done, you will end up with different amounts of tastiness of the final jar of pickles.

Every jar $i$ has brine value $a_i$. When you put pickles from jar $j$ to jar $i$, the tastiness of the final batch of pickles will be increased by $a_i \oplus a_j$, where $\oplus $ is defined as the bitwise XOR ¹.

The bitwise XOR of two integers $x$ and $y$ is calculated by looking at the binary representations of $x$ and $y$. The $i$’th bit of $x \oplus y$ is 1, if and only if exactly one if the $i$’th bits of $a$ and $b$ is 1. Bitwise XOR is available as an operator in both C++ and Python as ^.

As a pickle connoisseur, you would like to maximize the total tastiness after all the operations. Please find the an order of the jars and order of transfers such that the total tastiness is maximized.

Input

The first line of input contains the integer $N$ ($1 \leq N \leq 5 \cdot 10^5$), the number of jars of pickles.

The following line contains $N$ space separated integers $a_0, a_1, \dots , a_{N-1}$ ($1 \leq a_i \leq 10^{12}$), describing the brine values of the pickle jars.

Output

First, print an integer: the maximum possible tastiness value achievable.

To get full points, you also need to print a permutation and order of collisions that achieves this tastiness value. If get $75\% $ of the points for a given subtask, it suffices to only print the tastiness value.

On the second line, print the permutation of pickle jars. The $i$:th integer is the index of the pickle jar that should be placed at position $i$.

On the third line, print the integers $p_1, p_2, \dots , p_{N-1}$ describing the order that pickles should be transferred. First, assume that the jars have been permuted according to your permutation and then relabeled from $0$ to $N-1$ left to right. Then, each $p_i$ means that in transfer number $i$, the left jar is jar number $p_i$. Note that after jars are removed, the remaining jars are not relabeled.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Samples

In sample 1, we place the pickle jars in the order $[2,5,1]$. We then transfer jar $0$ to jar $1$, adding a tastiness of $2 \oplus 5=7$. Finally, we transfer jar $1$ to jar $2$, adding a tastiness of $5 \oplus 1=4$, resulting in $7+4=11$ tastiness in total. There is more than one way to achieve this amount of tastiness.

In sample 2, it suffices to use the order given in the input. Then, the transfers are as follows:

• Transfer jar $0$ to jar $1$, adding tastiness $5 \oplus 2=7$. The jars left have brine values $[2,2,5]$.

• Transfer jar $2$ to jar $3$, adding tastiness $2 \oplus 5=7$. The jars left have brine values $[2,5]$.

• Transfer jar $1$ to jar $3$, adding tastiness $2 \oplus 5=7$. The jar left has brine values $[5]$.

This results in $7+7+7=21$ total tastiness. Once again, there is more than one way to achieve this amount of tastiness.

3
1 2 5

11
1 2 0 
0 1 

4
5 2 2 5

21
0 1 2 3
0 2 1

6
10 2 15 12 3 2

65
1 2 5 3 4 0 
1 2 0 3 4