長さ $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}$）となります。最初のビットが最下位ビットであることに注意してください。

あなたの仕事は、文字集合 0, 1, ? 上の長さ $n$ のすべての文字列について一般化部分集合和を計算することです。出力全体は大きくなる可能性があるため、これらすべての和のビットごとの排他的論理和（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$ であることを容易に確認できます。