题目背景

凯瑞甘从帝国的围攻下，击毁了大天使号，乘着雷诺的飞船逃了出来，到了休伯利安号上。

“吉米？”凯瑞甘着急地四处寻找着。

“很抱歉，我们没能救出他”马特·霍纳向凯瑞甘走来。

“你丢下了他？”凯瑞甘回想起曾经的自己被蒙斯克丢下，便起了杀心，用灵能将马特抓了起来。

“不是的，凯瑞甘，我们受到了帝国的伏击，现在必须，马上离开，过会可以回头来找他”马特解释道。

“这里没有我们！你走吧，我自己去找他。”凯瑞甘放下了马特，回头坐着雷诺的回到了星球上。

“警告，警告，敌军突破能量场。”帝国的舰队突破了马特舰队设下的能量场，控制着钢铁舰队折越到了这里，并对休伯利安号发起猛烈的攻击。

“立即进行折越，我们必须马上离开！”马特·霍纳下令道。

题目描述

马特·霍纳想要控制休伯利安号进行折越，想要进行折越，就要激活休伯利安号上的所有 $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}$ 表示的是位运算中的按位异或运算。

输入格式

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

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

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

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

输出格式

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

3
1 2 3 
2 
10 
1

3
-1

1
0
1
1073741824000000

1073741824000000

提示

对于第一个询问，最大的 $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$。