UOJ Logo Universal Online Judge

UOJ

#681. 【UR #22】月球列车

附件下载 统计

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

工程师们设计出了一款非常特殊的引擎——月千引擎。这个引擎由 $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}$。

子任务编号 $n,m\leq$ $t=$ 分值
1 $10^3$ $1$ $30$
2 $10^5$ $1$ $30$
3 $2.5\times 10^5$ $0$ $30$
4 $2.5\times 10^5$ $1$ $10$

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

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