Дано масив $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)$ у прикладі 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$

Тепер легко перевірити, що вивід дорівнює $0$.