题目描述

阿历克斯附体的希尔芬、崩巴附体的切绘、蒸汽姬海老名与全能少女小埋在游乐场玩旋转咖啡杯。双鱼座的切绘占卜得到的幸运数字是 $3$，然而在游乐场却没有编号为 $3$ 的旋转咖啡杯。全能少女小埋想到了办法，旋转咖啡杯的编号构成了一个整数集合，小埋也给出了一个整数集合，并定义了一个操作。现在，她想知道操作后的旋转咖啡杯编号的最低位之和是多少，如果是 $3$，那么她就可以带着切绘去坐旋转咖啡杯啦！

（以上内容与题目内容无必然联系）

有两个非负整数组成的可重集合 $A$ 和 $B$。

现在你可以对 $A$ 中至多 $k$ 个元素进行操作。操作方法为：设你准备操作且未被操作过的 $A$ 中的元素是 $a$，你可以在 $B$ 中选取任意一个元素 $b$，将 $a$ 修改为 $a\oplus b$（这里 $\oplus$ 表示二进制按位异或），然后从 $B$ 中删去 $b$。

最终，你要使 $A$ 中所有元素的 $\mathrm{lowbit}$ 之和最小。正整数的 $\mathrm{lowbit}$ 定义为其二进制最低非零位的值，$0$ 的 $\mathrm{lowbit}$ 规定为 $0$，例如 $\mathrm{lowbit}(0)=0,\mathrm{lowbit}(1)=1,\mathrm{lowbit}(24)=8$。形式化地有： $$ \mathrm{lowbit}(x)= \begin{cases} \max({2^k:k\in \mathbb{N},2^k|x}) & x\in \mathbb{N}^+\ 0 & x=0 \end{cases} $$ （其中 $|$ 表示整除）

你需要求出操作后 $A$ 中所有元素的 $\mathrm{lowbit}$ 之和的可能的最小值。

输入格式

第一行一个整数 $n$ 表示 $A$ 的元素个数。
接下来一行 $n$ 个整数 ${a_i}$ 表示 $A$ 中元素。
接下来一行一个整数 $m$ 表示 $B$ 的元素个数。
接下来一行 $m$ 个整数 ${b_i}$ 表示 $B$ 中元素。
接下来一行一个整数 $k$。

输出格式

输出一行一个整数 $S$ 表示操作后 $A$ 中所有元素的 $\mathrm{lowbit}$ 之和的可能的最小值。

样例

input

5
6 18 14 1 13
5
7 7 8 8 15
3

output

5

${6,18,14,1,13}$ 的 $\mathrm{lowbit}$ 分别为 $2,2,2,1,1$，将 $6,18,14$ 分别与 $7,7,15$ 操作，得到新集合为 ${1,21,1,1,13}$，其 $\mathrm{lowbit}$ 分别为 $1,1,1,1,1$，答案为 $5$。

数据范围与提示

对于所有数据，$1\le n,m,k\le 1.2\times 10^6,0\le a_i,b_i\le 10^9$。