Problem Description

Given an array $a_i$ of length $2^n$ ($0 \leq i < 2^n$), you may perform cyclic shifts any number of times.

Find the maximum values of $\sum_{i=0}^{2^n-1} a_i \oplus i$, $\sum_{i=0}^{2^n-1} a_i \& i$, and $\sum_{i=0}^{2^n-1} a_i | i$. Here, $\oplus$, $\&$, and $|$ denote bitwise XOR, bitwise AND, and bitwise OR, respectively.

For an array $x_i$ of length $m$ ($0 \leq i < m$), the result after one cyclic shift is $x'_i$:

$$x'_i = \left\{ \begin{array}{ll} x_{i - 1} & i \neq 0 \\ x_{m - 1} & i = 0 \end{array}\right.$$

Input Format

The first line contains an integer $n$ ($1 \leq n \leq 20$), as described above.

The next line contains $2^n$ integers $a_i$ ($0 \leq a_i < 2^n$), representing the given array.

Output Format

Output one line with three integers separated by spaces, which are the maximum values of $\sum_{i=0}^{2^n-1} a_i \oplus i$, $\sum_{i=0}^{2^n-1} a_i \& i$, and $\sum_{i=0}^{2^n-1} a_i | i$.

2
1 3 2 2

8 5 11

4
1 1 4 5 1 4 1 9 1 9 8 1 0 0 0 0

149 41 157

Hint

Translated by ChatGPT 5