Gefið er fylki $a_0, a_1, \dots, a_{2^n-1}$ af lengd $2^n$. Fyrir streng $q$ af lengd $n$ yfir stafrófið 0, 1, ? (1-vísað), skilgreinum við „alhæfðu hlutmengjasummuna“ $S(q)$ sem summu $a_j$ yfir alla vísa $j$ sem uppfylla:

• Fyrir hvert $1 \le k \le n$, ef $q_k = \texttt{0}$ þá er $k$-ti bitinn í $j$ jafn $0$.
• Fyrir hvert $1 \le k \le n$, ef $q_k = \texttt{1}$ þá er $k$-ti bitinn í $j$ jafn $1$.
• Ef $q_k = \texttt{?}$ þá er engin skorða á $k$-ta bitann í $j$.

Til dæmis, þegar $n = 3$ og $q = \texttt{0?1}$, þá er alhæfða hlutmengjasumman $S(q) = a_4 + a_6$ ($\texttt{100}$ og $\texttt{110}$ í tvíundakerfi). Athugið að fyrsti bitinn er lægsti bitinn.

Verkefni þitt er að reikna alhæfðu hlutmengjasummuna fyrir hvern streng af lengd $n$ yfir stafrófið 0, 1, ?. Þar sem heildarúttakið getur verið stórt þarftu aðeins að prenta bitavísað XOR (bitwise XOR) af öllum þessum summum.

Inntak

Fyrsta línan í inntakinu inniheldur heiltölu $n$ ($1 \le n \le 16$).

Önnur línan í inntakinu inniheldur $2^n$ heiltölur $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), innihald fylkisins $a$.

Úttak

Prentaðu heiltölu sem táknar bitavísað XOR allra alhæfðra hlutmengjasummna.

Dæmi

Dæmi um inntak 1

1
3 5

Dæmi um úttak 1

14

Dæmi um inntak 2

2
2 6 8 8

Dæmi um úttak 2

0

Athugasemd

Eftirfarandi eru fyrirspurnarstrengirnir $q$ og samsvarandi alhæfðar hlutmengjasummur þeirra $S(q)$ í dæmi 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$

Nú er auðvelt að staðfesta að úttakið er $0$.