Description

Houraisan Kaguya (Kaguya) has a bunch of numbers.

Kaguya has $n$ non-negative integers $a_1,a_2\cdots a_n$. Since Kaguya went to play a Gal Game, she hopes that you, who are wise, can help.

• You need to divide these numbers into several groups, such that each of the $n$ numbers is assigned to exactly one group, and each group contains at least one number.

Define the weight of a group as the xor sum of all numbers in that group. Please find a grouping plan that minimizes the sum of the weights of all groups, and output this minimum value.

Input Format

The first line contains a positive integer $n$, representing the number of given non-negative integers.

The next line contains $n$ non-negative integers $a_1,a_2\cdots a_n$.

Output Format

Output one line with one integer representing the answer.

3
1 2 5

6

6
9 18 36 25 9 32

15

Hint

Explanation for Sample $1$:

One optimal grouping plan is:

• Put the $1$st number and the $3$rd number into one group, whose weight is $1\oplus 5 = 4$.
• Put the $2$nd number into one group, whose weight is $2$.

The sum of the weights of all groups is $4 + 2 = 6$. It can be proven that there is no grouping plan with a smaller total weight sum.

Explanation for Sample $2$:

One optimal grouping plan is:

• Put the $1$st number and the $5$th number into one group, whose weight is $9\oplus 9 = 0$.
• Put the $2$nd number and the $4$th number into one group, whose weight is $18\oplus 25 = 11$.
• Put the $3$rd number and the $6$th number into one group, whose weight is $36\oplus 32 = 4$.

The sum of the weights of all groups is $0 + 11 + 4 = 15$. It can be proven that there is no grouping plan with a smaller total weight sum.

Subtasks

• For $80\%$ of the testdata, $n\leq 15$.
• For $100\%$ of the testdata, $n\leq 10^6,a_i \leq 10^9$.

Source

Lost Home 2019 League (MtOI2019) T1

Problem setter: disangan233

Translated by ChatGPT 5