Дан массив $a_0, a_1, \dots, a_{2^n-1}$ длины $2^n$. Для строки $q$ длины $n$ над алфавитом 0, 1, ? (в 1-индексации) определим «обобщённую сумму подмножества» $S(q)$ как сумму $a_j$ по всем индексам $j$, удовлетворяющим следующим условиям:

• Для каждого $1 \le k \le n$, если $q_k = \texttt{0}$, то $k$-й бит числа $j$ равен $0$.
• Для каждого $1 \le k \le n$, если $q_k = \texttt{1}$, то $k$-й бит числа $j$ равен $1$.
• Если $q_k = \texttt{?}$, то на $k$-й бит числа $j$ нет никаких ограничений.

Например, при $n = 3$ и $q = \texttt{0?1}$ обобщённая сумма подмножества равна $S(q) = a_4 + a_6$ (в двоичной записи $\texttt{100}$ и $\texttt{110}$). Обратите внимание, что первый бит является младшим битом.

Ваша задача — вычислить обобщённую сумму подмножества для каждой строки длины $n$ над алфавитом 0, 1, ?. Поскольку общий объём вывода может быть велик, вам нужно вывести только побитовый XOR всех этих сумм.

Входные данные

Первая строка входных данных содержит целое число $n$ ($1 \le n \le 16$).

Вторая строка входных данных содержит $2^n$ целых чисел $a_0, a_1, \dots, a_{2^n-1}$ ($0 \le a_i \le 9$) — элементы массива $a$.

Выходные данные

Выведите одно целое число — побитовый XOR всех обобщённых сумм подмножеств.

Примеры

Пример ввода 1

1
3 5

Пример вывода 1

14

Пример ввода 2

2
2 6 8 8

Пример вывода 2

0

Примечание

Ниже приведены строки запросов $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$.