#P17176. 歪歪01串

歪歪01串

1004. 歪歪01串

题目描述

歪歪最近喜欢上了 01 串相关的问题。

歪歪有一个长度为 nn 的数组 aa ,其中第 ii 个元素为 aia_i ;同时她有另一个长度相同的数组 bb, 初始都为 00 。

歪歪定义数组 aa 的权值为:⨁i=1nbiai\bigoplus_{i=1}^{n} b_{i} a_{i} 。其中 ⨁\bigoplus 表示异或操作。

同时歪歪还能对数组 bb 使用魔法,即她有一个数 lenlen ,可以对数组 bb 任意长度为 lenlen 的连续子数组作元素翻转,即 00 变成 11 , 11 变成 00 。

现在歪歪会问你 qq 次问题,每次问题都会给你一个数 xx ,她想知道对于每一个数 xx ,她对数组 bb 做若干次魔法操作后能得到数组 aa 权值异或上 xx 的值最大是多少呢?

输入格式

第一行输入测试用例 TT 。

对于每一个测试用例,第一行输入三个正整数 n,len,qn,len,q ,分别表示数组的长度、歪歪的魔法能操作子数组的长度以及歪歪问问题的次数 qq 。

接下来一行输入 nn 个整数 aia_i ,为数组 aa 的元素值。

接下来 qq 行,每行输入一个整数 xx ,表示歪歪每个问题询问的 xx 。

数据保证:T≤10T\leq10,1≤n,q≤1051\leq n,q\leq10^5,1≤len≤n1\leq len \leq n,0≤ai,x≤10180\leq a_i,x\leq10^{18}。

输出格式

对于每组测试用例,输出 qq 行,每行表示歪歪问你该问题的答案。

样例输入

2
5 3 2
3 2 5 8 14
5
3
6 3 2
3 4 5 7 14 19
7
44

样例输出

14
15
31
62

来源:2026杭电多校-测试专用(杭电第1场-内测) 原题链接:http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1004