P6747 『MdOI R3』Teleport

凯瑞甘从帝国的围攻下，击毁了大天使号，乘着雷诺的飞船逃了出来，到了休伯利安号上。 “吉米？”凯瑞甘着急地四处寻找着。 “很抱歉，我们没能救出他”马特·霍纳向凯瑞甘走来。 “你丢下了他？”凯瑞甘回想起曾经的自己被蒙斯克丢下，便起了杀心，用灵能将马特抓了起来。 “不是的，凯瑞甘，我们受到了帝国的伏击，现在必须，马上离开，过会可以回头来找他”马特解释道。 “这里没有我们！你走吧，我自己去找他。”凯瑞甘放下了马特，回头坐着雷诺的回到了星球上。 “警告，警告，敌军突破能量场。”帝国的舰队突破了马特舰队设下的能量场，控制着钢铁舰队折越到了这里，并对休伯利安号发起猛烈的攻击。 “立即进行折越，我们必须马上离开！”马特·霍纳下令道。

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

无

无

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