C-异或与位移_牛客练习赛133

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 我有异或症。

$\hspace{15pt}$ 不过也没关系，我们这里有一个关于异或与位移的问题，你能够解决她吗？

$\hspace{15pt}$

$\hspace{15pt}$ 对于小川给定的由 $n$ 个整数构成的序列 $a=\{a_1,a_2,\cdots,a_n\}$ 和一个整数 $k$ ，满足 $-k \lt a_i \lt k$ 且 $a_i \neq 0$ 。

$\hspace{15pt}$ 定义函数 $F(x)$ 如下：
$\hspace{23pt}\bullet\,$ 记 $B_0 = x$ ；
$\hspace{23pt}\bullet\,$ 令 $B_i = \left(B_{i-1} \oplus \left\lfloor B_{i-1} \times 2^{a_i}\right\rfloor\right) \bmod 2^k$ ；
$\hspace{23pt}\bullet\,$ 那么 $F(x) = B_n$ 。

$\hspace{15pt}$ 小川需要你回答 $m$ 个询问，每个询问为：
$\hspace{23pt}\bullet\,$ 给定一个非负整数 $y$ ，找到一个非负整数 $x$ 满足 $0\le x<2^k$ 且 $y=F(x)$ ；如果没有这样的 $x$ ，则输出 $-1$ 。
$\hspace{15pt}$ 注意：我们将以无前缀 $0$ 的二进制格式从最高位到最低位输入 $y$ （当 $y=0$ 时，依旧会读入一个 $0$ ），你需要以无前缀 $0$ 的二进制格式从最高位到最低位输出 $x$ （如果答案为 $-1$ ，则直接输出 $-1$ 即可；如果答案为 $0$ ，你依旧需要输出一个 $0$ ）。

$\hspace{15pt}$ 在本题中， $\oplus$ 表示异或操作， $\lfloor x\rfloor$ 表示将 $x$ 向下取整。

输入描述:

第一行输入三个整数  代表序列种的元素数量、询问次数、序列元素的取值范围。 
第二行输入  个整数  代表序列中的元素。 
此后  行，每行从最高位到最低位输入一个无前缀  的二进制格式的整数 （当  时，依旧会读入一个 ）代表一次询问。

输出描述:

对于每一次询问，新起一行。从最高位到最低位输出一个无前缀  的二进制格式的整数，表示对应的询问的答案（如果答案为 ，则直接输出  即可；如果答案为 ，你依旧需要输出一个 ）。

示例1

输入

复制

输出

复制

101
1

说明

对于第一个询问，当  时，，，所以 ，满足；
对于第二个询问，当  时，，，所以 ，满足。

示例2

输入

复制

3 1 10000
1 1 4
0

输出

复制