Problem Description

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

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$, where $\oplus$, $\&$, and $|$ represent bitwise XOR, bitwise AND, and bitwise OR, respectively.

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

$$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 of input contains an integer $n$ ($1 \leq n \leq 20$), as described in the problem.

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, representing 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$.

Sample Input and Output

Sample Input #1

2
1 3 2 2

Sample Output #1

8 5 11

Sample Input #2

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

Sample Output #2

149 41 157

见题面 Input 部分

见题面 Output 部分