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

工程师们设计出了一款非常特殊的引擎——月千引擎。这个引擎由 $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^{\prime }$，表示第 $i$ 个询问的速度 $v_i=v_i^{\prime }\oplus (t\times \lfloor \frac{\mathrm{lastans}}{2^{20}}\rfloor )$，其中 $\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\mathrm{\%}$ 的数据，$1\le n,m\le 2.5\times {10}^5,t\in \{0,1\},0\le a_i,v_i^{\prime }<2^{60}$。

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$