UOJ Logo

NOI.AC

1S 512MB

#1510. k 大异或和

Statistics

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

样例输入

3
1 2 3
5
1 2 3 4 5

样例输出

样例输出

0
1
2
3
-1

数据范围与提示

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