길이가 $2^n$인 배열 $a_0, a_1, \dots, a_{2^n-1}$이 주어집니다. 알파벳 0, 1, ?로 이루어진 길이 $n$인 문자열 $q$ (1-indexed)에 대해, "일반화된 부분집합 합" $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}$)입니다. 첫 번째 비트가 최하위 비트(lowest bit)임에 유의하세요.

당신의 과제는 알파벳 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$)이 주어집니다.

출력

모든 일반화된 부분집합 합들의 비트 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$임을 쉽게 확인할 수 있습니다.