Gegeben ist ein Array $a_0, a_1, \dots, a_{2^n-1}$ der Länge $2^n$. Für eine Zeichenkette $q$ der Länge $n$ über dem Alphabet 0, 1, ? (1-indiziert) definieren wir die „verallgemeinerte Teilmengensumme“ $S(q)$ als die Summe aller $a_j$ über alle Indizes $j$, die Folgendes erfüllen:
- Für jedes $1 \le k \le n$ gilt: Wenn $q_k = \texttt{0}$ ist, dann ist das $k$-te Bit von $j$ gleich $0$.
- Für jedes $1 \le k \le n$ gilt: Wenn $q_k = \texttt{1}$ ist, dann ist das $k$-te Bit von $j$ gleich $1$.
- Wenn $q_k = \texttt{?}$ ist, gibt es keine Einschränkung für das $k$-te Bit von $j$.
Zum Beispiel ist für $n = 3$ und $q = \texttt{0?1}$ die verallgemeinerte Teilmengensumme $S(q) = a_4 + a_6$ (binär $\texttt{100}$ und $\texttt{110}$). Beachte, dass das erste Bit das niederwertigste Bit ist.
Deine Aufgabe ist es, die verallgemeinerte Teilmengensumme für jede Zeichenkette der Länge $n$ über dem Alphabet 0, 1, ? zu berechnen. Da die Gesamtausgabe sehr groß sein kann, musst du nur das bitweise XOR aller dieser Summen ausgeben.
Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl $n$ ($1 \le n \le 16$).
Die zweite Zeile der Eingabe enthält $2^n$ ganze Zahlen $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), den Inhalt des Arrays $a$.
Ausgabe
Gib eine ganze Zahl aus, die das bitweise XOR aller verallgemeinerten Teilmengensummen bezeichnet.
Beispiele
Beispieleingabe 1
1 3 5
Beispielausgabe 1
14
Beispieleingabe 2
2 2 6 8 8
Beispielausgabe 2
0
Hinweis
Im Folgenden sind die Anfrage-Zeichenketten $q$ und ihre zugehörigen verallgemeinerten Teilmengensummen $S(q)$ aus Beispiel 2 aufgeführt:
- $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$
Nun lässt sich leicht überprüfen, dass die Ausgabe $0$ ist.