Ci viene dato un array $a_0, a_1, \dots, a_{2^n-1}$ di lunghezza $2^n$. Per una stringa $q$ di lunghezza $n$ sull'alfabeto 0, 1, ? (indicizzata da 1), definiamo la "somma di sottoinsiemi generalizzata" $S(q)$ come la somma di $a_j$ su tutti gli indici $j$ che soddisfano:

• Per ogni $1 \le k \le n$, se $q_k = \texttt{0}$ allora il $k$-esimo bit di $j$ è $0$.
• Per ogni $1 \le k \le n$, se $q_k = \texttt{1}$ allora il $k$-esimo bit di $j$ è $1$.
• Se $q_k = \texttt{?}$ non c'è alcuna restrizione sul $k$-esimo bit di $j$.

Ad esempio, quando $n = 3$ e $q = \texttt{0?1}$, la somma di sottoinsiemi generalizzata è $S(q) = a_4 + a_6$ (in binario $\texttt{100}$ e $\texttt{110}$). Nota che il primo bit è il bit meno significativo.

Il tuo compito è calcolare la somma di sottoinsiemi generalizzata per ciascuna stringa di lunghezza $n$ sull'alfabeto 0, 1, ?. Poiché l'output totale può essere grande, devi solamente stampare lo XOR bit a bit (bitwise XOR) di tutte queste somme.

Input

La prima riga dell'input contiene un intero $n$ ($1 \le n \le 16$).

La seconda riga dell'input contiene $2^n$ interi $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), il contenuto dell'array $a$.

Output

Stampa un intero che indica lo XOR bit a bit di tutte le somme di sottoinsiemi generalizzate.

Esempi

Input di esempio 1

1
3 5

Output di esempio 1

14

Input di esempio 2

2
2 6 8 8

Output di esempio 2

0

Note

Di seguito sono riportate le stringhe di query $q$ e le corrispondenti somme di sottoinsiemi generalizzate $S(q)$ nell'esempio 2:

• $q = \texttt{00}, S(q) = a_0 = 2$
• $q = \texttt{10}, S(q) = a_1 = 6$
• $q = \texttt{?0}, S(q) = a_0 + a_1 = 2 + 6 = 8$
• $q = \texttt{01}, S(q) = a_2 = 8$
• $q = \texttt{11}, S(q) = a_3 = 8$
• $q = \texttt{?1}, S(q) = a_2 + a_3 = 16$
• $q = \texttt{0?}, S(q) = a_0 + a_2 = 10$
• $q = \texttt{1?}, S(q) = a_1 + a_3 = 14$
• $q = \texttt{??}, S(q) = a_0 + a_1 + a_2 + a_3 = 24$

Ora è facile verificare che l'output è $0$.