#4622. 模板.k 大异或和 传统1000 ms

模板.k 大异或和 传统1000 ms

Description

这是一道模板题。

给由 n n 个数组成的一个可重集 S S ,每次给定一个数 k k ,求一个集合 TS T \subseteq S ,使得集合 T T S S 的所有非空子集的不同的异或和中,其异或和 $ T_1 \mathbin{\text{xor}} T_2 \mathbin{\text{xor}} \ldots \mathbin{\text{xor}} T_{|T|} $ 是第 k k 小的。

Input

第一行一个数 n n 。 第二行 n n 个数,表示集合 S S 。 第三行一个数 m m ,表示询问次数。 第四行 m m 个数,表示每一次询问的 k k

Output

输出 m m 行,对应每一次询问的答案,第 k k 小的异或和。如果集合 S S 的所有非空子集中,不同的异或和数量不足 k k ,输出 1 -1

Samples

3
1 2 3
5
1 2 3 4 5
0
1
2
3
-1

Limitation

$ 1 \leq n, m \leq 10 ^ 5, 0 \leq S_i \leq 2 ^ {50} $