Final Exam

题号：NC206676
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Final exam is coming. To review the math, teacher gives you a difficult problem.

Teacher will give you n integers $a_i$ and an integer m. You should answer the maximum k satisfying $\sum (a_i \oplus k) \leq m$ . If such k does not exist, please answer -1.

Now this problem becomes more difficult. You should process Q queries of m to the same sequence of n and $a_i$ .

输入描述:

The first line contains an integer $n ~ (1 \leq n \leq 10^5)$ .

The second line contains n integers $a_i ~ (0 \leq a_i \leq 2^{30})$ .

The third line contains an integer $Q ~ (1 \leq Q \leq 10^5)$ denoting the count of query.

Following Q lines each line contains an integer $m ~ (0 \leq m \leq 2^{30} \times 10^6)$ .

输出描述:

For each query, output a line containing the answer for the maxinum k.

示例1

输入

复制

输出

复制

3
-1

示例2

输入

复制

1
0
1
1073741824000000

输出

复制

1073741824000000