在这个问题中，给你一个字节数组 $a$。你需要做的是对它的子序列进行哈希。幸运的是，你不需要在无数种哈希方法中做出痛苦的选择，因为我们已经为你做好了决定。

如果我们把子序列看作数组 $a$ 的下标的严格递增序列 $s$，那么该子序列的哈希函数通过以下公式计算：

$$Hash(s) = \sum_{0 \le i < \operatorname{sizeof}(s)} (i \oplus a_{s_i})$$

这里，$\oplus$ 表示按位异或（XOR）操作。如果需要说明，请参阅“说明”部分。

由于你最终需要将这些值存储在一个数组中，你想知道在数组 $a$ 的所有子序列中，哈希函数可能达到的最大值。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 100\,000$），表示数组 $a$ 中的字节数。

第二行包含 $n$ 个用十六进制表示并用空格隔开的字节。每个字节恰好由两个十六进制数字（0...F）表示。

输出格式

输出一个整数，表示数组 $a$ 的子序列所能达到的哈希函数的最大可能值。

样例

输入样例 1

3
03 00 1B

输出样例 1

29

输入样例 2

3
01 00 02

输出样例 2

4

说明

在第一个样例中，最佳选择之一是选择子序列 03 00 1B。

$hash = (0 \oplus 3) + (1 \oplus 0) + (2 \oplus 27) = 3 + 1 + 25 = 29$

在第二个样例中，唯一最佳的选择是选择子序列 01 02。

$hash = (0 \oplus 1) + (1 \oplus 2) = 1 + 3 = 4$

这里我们向你解释什么是按位异或（XOR）操作。如果你有两个整数 $x$ 和 $y$，考虑它们的二进制表示（可能带有前导零）：$x_k \dots x_2 x_1 x_0$ 和 $y_k \dots y_2 y_1 y_0$。这里，$x_i$ 是数字 $x$ 的第 $i$ 位，$y_i$ 是数字 $y$ 的第 $i$ 位。设 $r = x \oplus y$ 为 $x$ 和 $y$ 进行异或操作的结果。那么 $r$ 被定义为 $r_k \dots r_2 r_1 r_0$，其中：

$$r_i = \begin{cases} 1, & \text{如果 } x_i \ne y_i \\ 0, & \text{如果 } x_i = y_i \end{cases}$$