P6747 "MdOI R3" Teleport

Kerrigan escaped from the Empire’s siege after destroying the Archangel, and fled on Raynor’s ship to the Hyperion. “Jimmy?” Kerrigan anxiously looked around everywhere. “I’m sorry, we couldn’t save him.” Matt Horner walked up to Kerrigan. “You left him behind?” Kerrigan recalled how she had once been abandoned by Mengsk, and murderous intent rose. She used her psionic power to seize Matt. “No, Kerrigan. We were ambushed by the Empire. We have to leave now. We can come back later to look for him.” Matt explained. “There is no ‘we’ here! You go. I’ll find him myself.” Kerrigan released Matt, turned around, and went back to the planet in Raynor’s ship. “Warning, warning, enemy forces have broken through the energy field.” The Empire fleet broke through the energy field set up by Matt’s fleet, warped here while controlling the steel fleet, and launched a fierce attack on the Hyperion. “Warp immediately. We must leave at once!” Matt Horner ordered.

Matt Horner wants to control the Hyperion to perform a warp. To warp, he must activate all $n$ nodes on the Hyperion. There are $n$ nodes on the Hyperion. The $i$-th node has $a_i$ energy. To activate them, Matt Horner will consume $k\times n$ units of terrazine. These $k\times n$ units of terrazine are evenly distributed to the $n$ nodes. After each node receives $k$ units of terrazine, it will be triggered and gain $a_i \operatorname{xor} k$ units of high energy. The total sum of high energy over all nodes is the warp cost $S$. To warp as fast as possible, Matt Horner decides to use as much as $k\times n$ units of terrazine as possible. Unfortunately, if too much terrazine is used so that the cost $S$ exceeds the limit $m$, the Hyperion will be overloaded and eventually explode. Now, your task is to help Matt Horner find the maximum $k$ such that the Hyperion can warp away as fast as possible while staying safe. If it is impossible to warp safely under any circumstances, output $-1$. Here, $\operatorname{xor}$ denotes the bitwise XOR operation.

The first line contains an integer $n$, the number of nodes. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, representing the energy of each node. The third line contains an integer $q$, the number of queries. The next $q$ lines describe the queries. Each line contains one number $m$.

For each query, output one line containing a non-negative integer, the maximum $k$. If there is no solution, output $-1$.

For the first query, the maximum $k$ is $3$. At this time, $S=2+1+0=3 \le 10$. It can be proven that no larger $k$ satisfies the condition. For the second query, there is no $k$ that satisfies the condition. | Test Point | $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$ | **This problem does not use bundled tests.** The Constraints for all test points are shown above. For all data, $0