Description

马特·霍纳想要控制休伯利安号进行折越，想要进行折越，就要激活休伯利安号上的所有 $n$ 个位点。

休伯利安号上有 $n$ 个位点，每个位点有 $a_i$ 点能量，为了激活，马特·霍纳会消耗 $k\times n$ 点地嗪，这 $k\times n$ 点地嗪会平均分给 $n$ 个位点，每个位点在接受 $k$ 点地嗪后会激发，得到 $a_i \operatorname{xor} k$ 点高能，所有位点的高能总和为这次折越的消耗 $S$。

为了能够快速的进行折越，马特·霍纳决定用最多的 $k\times n$ 点地嗪，但可惜的是，如果地嗪使用太多，使得消耗 $S$ 超过限制值 $m$ ，那么休伯利安号就会不堪重负，最终爆炸。

现在，你的任务是帮助马特·霍纳找到这个最大的 $k$ ，使得休伯利安号能在安全的前提下尽可能快的折越走。如果任何情况下都不能安全的折越走，则输出 $-1$ 。

这里的 $\operatorname{xor}$ 表示的是位运算中的按位异或运算。

Input Format

第一行一个整数 $n$ 表示位点数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个位点拥有的能量。

第三行一个数 $q$ 表示询问次数。

接下来 $q$ 行表示 $q$ 次询问，每行一个数 $m$。

Output Format

对于每次询问输出一行一个非负整数，表示最大的 $k$。若无解，输出 $-1$ 。

3
1 2 3 
2 
10 
1

3
-1

1
0
1
1073741824000000

1073741824000000

Hint

对于第一个询问，最大的 $k$ 为 $3$ ，此时 $S=2+1+0=3 \le 10$ ，可证没有更大的 $k$ 满足条件。

对于第二个询问，没有任何 $k$ 满足条件。 |数据点 |$n$ |$a_i$ | $m$ | $q$ | | :------: | :------: | :-------: | :-------: | :----------: | |$1$|$\le 10$|$\le 2^{20}$| $\le 2^{20}$| $=1$ | |$2$| $\le 10^3$|$\le10^3$|$\le10^3$|$\le 10^3$| |$3$|$\le 10^3$ | $\le 2^{30}$ | $\le 10^3$ | $\le 10^3$ | |$4\sim 6$| $\le 10^5$| $\le 2^{20}$ | $\le 10^6$ | $\le 10^5$ | |$7\sim 10$| $\le 10^5$ | $\le 2^{30}$ | $\le 2^{30}\times10^6$ | $\le 10^5$ | 本题不进行捆绑测试。

所有测试点的数据范围如上所示。对于所有数据，$0<n,q\leq 10^5,\ 0\leq a_i\leq 2^{30},\ 0\leq m\leq 2^{30}\times 10^6$。