Se nos da un arreglo $a_0, a_1, \dots, a_{2^n-1}$ de longitud $2^n$. Para una cadena $q$ de longitud $n$ sobre el alfabeto 0, 1, ? (indexada desde 1), definimos la «suma de subconjunto generalizada» $S(q)$ como la suma de $a_j$ sobre todos los índices $j$ que satisfacen:

• Para cada $1 \le k \le n$, si $q_k = \texttt{0}$, entonces el $k$-ésimo bit de $j$ es $0$.
• Para cada $1 \le k \le n$, si $q_k = \texttt{1}$, entonces el $k$-ésimo bit de $j$ es $1$.
• Si $q_k = \texttt{?}$, no hay ninguna restricción sobre el $k$-ésimo bit de $j$.

Por ejemplo, cuando $n = 3$ y $q = \texttt{0?1}$, la suma de subconjunto generalizada es $S(q) = a_4 + a_6$ ($\texttt{100}$ y $\texttt{110}$ en binario). Ten en cuenta que el primer bit es el bit menos significativo.

Tu tarea es calcular la suma de subconjunto generalizada para cada cadena de longitud $n$ sobre el alfabeto 0, 1, ?. Como la salida total puede ser muy grande, solo necesitas imprimir el XOR bit a bit (bitwise XOR) de todas estas sumas.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 16$).

La segunda línea de la entrada contiene $2^n$ enteros $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), el contenido del arreglo $a$.

Salida

Imprime un entero que denote el XOR bit a bit de todas las sumas de subconjunto generalizadas.

Ejemplos

Entrada de ejemplo 1

1
3 5

Salida de ejemplo 1

14

Entrada de ejemplo 2

2
2 6 8 8

Salida de ejemplo 2

0

Nota

Las siguientes son las cadenas de consulta $q$ y sus correspondientes sumas de subconjunto generalizadas $S(q)$ en el ejemplo 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$

Ahora es fácil verificar que la salida es $0$.