伏特找到了跳蚤国顶尖的工程师们，请他们设计月球列车的引擎。

工程师们设计出了一款非常特殊的引擎——月千引擎。这个引擎由 $n$ 个部件组成，每个部件有一个功耗参数 $a_i$。

当引擎以 $x$ 的速度行进时，引擎的总功耗为 $\oplus_{i=1}^n (a_i+x)$，即 $(a_1 + x) \oplus (a_2 + x) \oplus \cdots \oplus (a_n + x)$，其中 $\oplus$ 表示异或。

现在伏特设置了 $m$ 种不同的速度，你需要快速算出引擎的功耗。由于伏特的暴脾气，你有可能需要得到每一个速度后立马输出答案。

输入格式

第一行三个整数 $n, m, t$，表示引擎部件数，询问数量以及加密参数。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示部件的功耗参数。

接下来 $m$ 行，第 $i$ 行输入 $v'_i$，表示第 $i$ 个询问的速度 $v_i=v'_i \oplus \left(t \times \left\lfloor\frac{\mathrm{lastans}}{2^{20}}\right\rfloor\right)$，其中 $\oplus$ 表示异或，$\mathrm{lastans}$ 表示上一个询问的输出（如果没有则为 $0$）。

输出格式

输出 $m$ 行，第 $i$ 行一个整数 $w_i$ 表示第 $i$ 次询问的功耗。

样例一

input

2 2 0
1 2
2
3

output

7
1

explanation

第一次询问的输出为 $(1+2)\oplus(2+2)=3\oplus 4=7$。

第一次询问的输出为 $(1+3)\oplus(2+3)=4\oplus 5=1$。

样例二、三

见附件下载。

限制与约定

对于 $100\%$ 的数据，$1\leq n, m\leq 2.5\times 10^5, t\in \{0, 1\}, 0\leq a_i,v'_i\lt 2^{60}$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$