给定一个长度为 $2^n$ 的数组 $a_0, a_1, \dots, a_{2^n-1}$。对于一个长度为 $n$ 且字符集为 0, 1, ? 的字符串 $q$（下标从 1 开始），定义“广义子集和” $S(q)$ 为满足以下条件的所有下标 $j$ 的 $a_j$ 之和：

• 对于每个 $1 \le k \le n$，如果 $q_k = 0$，则 $j$ 的第 $k$ 位为 0。
• 对于每个 $1 \le k \le n$，如果 $q_k = 1$，则 $j$ 的第 $k$ 位为 1。
• 如果 $q_k = ?$，则对 $j$ 的第 $k$ 位没有限制。

例如，当 $n = 3$ 且 $q = 0?1$ 时，广义子集和为 $S(q) = a_4 + a_6$（二进制分别为 100 和 110）。注意，第一位是最低位。

你的任务是对于所有长度为 $n$ 且字符集为 0, 1, ? 的字符串，计算其广义子集和。由于总输出可能很大，你只需要输出所有这些和的按位异或（bitwise 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$ 中的元素。

输出格式

输出一个整数，表示所有广义子集和的按位异或值。

样例

输入样例 1

1
3 5

输出样例 1

14

输入样例 2

2
2 6 8 8

输出样例 2

0

说明

以下是样例 2 中查询字符串 $q$ 及其对应的广义子集和 $S(q)$：

• $q = 00, S(q) = a_0 = 2$
• $q = 10, S(q) = a_1 = 6$
• $q = ?0, S(q) = a_0 + a_1 = 2 + 6 = 8$
• $q = 01, S(q) = a_2 = 8$
• $q = 11, S(q) = a_3 = 8$
• $q = ?1, S(q) = a_2 + a_3 = 16$
• $q = 0?, S(q) = a_0 + a_2 = 10$
• $q = 1?, S(q) = a_1 + a_3 = 14$
• $q = ??, S(q) = a_0 + a_1 + a_2 + a_3 = 24$

此时很容易验证输出为 0。