Description

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.

Input Format

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$.

Output Format

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

3
1 2 3 
2 
10 
1

3
-1

1
0
1
1073741824000000

1073741824000000

Hint

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.

This problem does not use bundled tests.

The Constraints for all test points are shown above. For all data, $0<n,q\leq 10^5,\ 0\leq a_i\leq 2^{30},\ 0\leq m\leq 2^{30}\times 10^6$.

Translated by ChatGPT 5