Ұзындығы $2^n$ болатын $a_0, a_1, \dots, a_{2^n-1}$ массиві берілген. 0, 1, ? әліпбиінен құралған ұзындығы $n$ болатын $q$ жолы үшін (1-ден бастап нөмірленген) «жалпыланған ішкі жиын қосындысы» $S(q)$ деп келесі шарттарды қанағаттандыратын барлық $j$ индекстері бойынша алынған $a_j$ мәндерінің қосындысын атаймыз:

• Әрбір $1 \le k \le n$ үшін, егер $q_k = \texttt{0}$ болса, онда $j$ санының $k$-шы биті $0$ болады.
• Әрбір $1 \le k \le n$ үшін, егер $q_k = \texttt{1}$ болса, онда $j$ санының $k$-шы биті $1$ болады.
• Егер $q_k = \texttt{?}$ болса, онда $j$ санының $k$-шы битіне ешқандай шектеу қойылмайды.

Мысалы, $n = 3$ және $q = \texttt{0?1}$ болғанда, жалпыланған ішкі жиын қосындысы $S(q) = a_4 + a_6$ (екілік жүйеде $\texttt{100}$ және $\texttt{110}$) болады. Бірінші бит ең кіші разрядты бит екеніне назар аударыңыз.

Сіздің міндетіңіз — 0, 1, ? әліпбиінен құралған ұзындығы $n$ болатын әрбір жол үшін жалпыланған ішкі жиын қосындысын есептеу. Жалпы шығыс көлемі үлкен болуы мүмкін болғандықтан, осы қосындылардың барлығының разрядтық XOR (bitwise XOR) мәнін ғана шығаруыңыз керек.

Кіріс деректер

Кірістің бірінші жолында бір бүтін сан $n$ ($1 \le n \le 16$) берілген.

Кірістің екінші жолында $a$ массивінің элементтерін білдіретін $2^n$ бүтін сан $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$) берілген.

Шығыс деректер

Барлық жалпыланған ішкі жиын қосындыларының bitwise-XOR мәнін білдіретін бір бүтін санды шығарыңыз.

Мысалдар

1-мысал кіріс

1
3 5

1-мысал шығыс

14

2-мысал кіріс

2
2 6 8 8

2-мысал шығыс

0

Ескертпе

Төменде 2-мысалдағы $q$ сұраныс жолдары мен оларға сәйкес $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$

Енді жауаптың $0$ екенін оңай тексеруге болады.