On nous donne un tableau $a_0, a_1, \dots, a_{2^n-1}$ de longueur $2^n$. Pour une chaîne $q$ de longueur $n$ sur l'alphabet 0, 1, ? (indexée à partir de 1), on définit la « somme de sous-ensemble généralisée » $S(q)$ comme la somme des $a_j$ sur tous les indices $j$ qui vérifient :

• Pour chaque $1 \le k \le n$, si $q_k = \texttt{0}$, alors le $k$-ième bit de $j$ vaut $0$.
• Pour chaque $1 \le k \le n$, si $q_k = \texttt{1}$, alors le $k$-ième bit de $j$ vaut $1$.
• Si $q_k = \texttt{?}$, il n'y a aucune restriction sur le $k$-ième bit de $j$.

Par exemple, lorsque $n = 3$ et $q = \texttt{0?1}$, la somme de sous-ensemble généralisée est $S(q) = a_4 + a_6$ ($\texttt{100}$ et $\texttt{110}$ en binaire). Notez que le premier bit est le bit de poids faible.

Votre tâche consiste à calculer la somme de sous-ensemble généralisée pour chaque chaîne de longueur $n$ sur l'alphabet 0, 1, ?. Comme la sortie totale peut être volumineuse, vous devez uniquement afficher le XOR bit à bit (bitwise XOR) de toutes ces sommes.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 16$).

La deuxième ligne de l'entrée contient $2^n$ entiers $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), le contenu du tableau $a$.

Sortie

Affichez un entier représentant le XOR bit à bit de toutes les sommes de sous-ensembles généralisées.

Exemples

Exemple d'entrée 1

1
3 5

Exemple de sortie 1

14

Exemple d'entrée 2

2
2 6 8 8

Exemple de sortie 2

0

Note

Voici les chaînes de requête $q$ et leurs sommes de sous-ensembles généralisées correspondantes $S(q)$ dans l'exemple 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$

Il est maintenant facile de vérifier que la sortie vaut $0$.