Annettuna on taulukko $a_0, a_1, \dots, a_{2^n-1}$, jonka pituus on $2^n$. Merkkijonolle $q$, jonka pituus on $n$ ja joka koostuu aakkoston 0, 1, ? merkeistä (1-indeksoitu), määritellään "yleistetty osajoukon summa" $S(q)$ lukujen $a_j$ summana yli kaikkien indeksien $j$, jotka toteuttavat seuraavat ehdot:

• Jokaiselle $1 \le k \le n$, jos $q_k = \texttt{0}$, niin luvun $j$ $k$:s bitti on $0$.
• Jokaiselle $1 \le k \le n$, jos $q_k = \texttt{1}$, niin luvun $j$ $k$:s bitti on $1$.
• Jos $q_k = \texttt{?}$, luvun $j$ $k$:nnelle bitille ei ole rajoitusta.

Esimerkiksi, kun $n = 3$ ja $q = \texttt{0?1}$, yleistetty osajoukon summa on $S(q) = a_4 + a_6$ (binäärinä $\texttt{100}$ ja $\texttt{110}$). Huomaa, että ensimmäinen bitti on vähiten merkitsevä bitti.

Tehtäväsi on laskea yleistetty osajoukon summa jokaiselle pituutta $n$ olevalle merkkijonolle aakkostossa 0, 1, ?. Koska kokonaistuloste voi olla suuri, sinun tarvitsee tulostaa vain kaikkien näiden summien bittikohtainen XOR (bitwise XOR).

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 16$).

Syötteen toinen rivi sisältää $2^n$ kokonaislukua $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$), taulukon $a$ sisällön.

Tuloste

Tulosta kokonaisluku, joka ilmaisee kaikkien yleistettyjen osajoukon summien bittikohtaisen XOR-arvon.

Esimerkit

Esimerkkisyöte 1

1
3 5

Esimerkkituloste 1

14

Esimerkkisyöte 2

2
2 6 8 8

Esimerkkituloste 2

0

Huomautus

Seuraavassa on esimerkin 2 kyselymerkkijonot $q$ ja niitä vastaavat yleistetyt osajoukon summat $S(q)$:

• $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$

Nyt on helppo tarkistaa, että tuloste on $0$.