[Login|Register]
Problems

Status

Rank

Problem 1409
团队密码
Time Limit: 1000ms
Memory Limit: 65536kb
Description
Big Pot是一支充满爱与激情的队伍,队员之间相互通讯时使用一种特殊的密码:他们将想要说的内容转化为数字,埋藏在密码串之间,每个密码串格式如下:开头是2个正整数n和m,后面跟着n个正整数a[1],a[2], .. ,a[n]和m个正整数b[1],b[2], .. ,b[m].解码规则如下:对于每个b[i],解码出2个数字明文c[i][1]和c[i][2],其中c[i][1]是a[1]到a[b[i]]中所有数字的去重按位异或,c[i][2]是从a[b[i]]到a[n]中所有数字的去重按位异或.去重按位异或是这样的一种运算:对于数列data[first]到data[last],去掉其中多余的重复数字,仅保留第一个,对其余数字进行按位异或,例如数列1,2,3,2,1,2的去重按位异或等于数列1,2,3的按位异或,其结果为1^2^3=0.
以上描述中所有区间均为闭区间.
有一天Coach Ray在监督Big Pot训练,发现队员们在使用那种奇怪的密码通信,Coach Ray认为队员们又在淘气地开小差,打算对他们的通信进行监听.他拦截到了一些完整的密码串,但是Coach Ray忙于刷题,没空亲自解码这些密码串,于是机智的他找到了你,希望你能将这些密码串解码为数字.至于这些数字代表什么含义,Coach Ray才不会告诉你呢.
Input
多组输入,处理到文件结尾为止
每组数据包括:
第1行:2个用空格分开的正整数n m,(1 <= n,m <= 100000)
第2行:n个用空格分开的正整数a[1] a[2] .. a[n],(1 <= a[i] <= 100000, 1 <= i <= n)
第3到第m+2行:第j+2行包括一个正整数b[j],(1 <= b[j] <= 100000, 1 <= j <= m)
Output
对于每组输入,输出m行,第i行包括2个用空格分开的整数c[i][1] c[i][2],其含义如题目描述.
Sample Input
6 6
1 2 3 2 1 2
1
2
3
4
5
6
Sample Output
1 0
3 0
0 0
0 3
0 3
0 2
Source
wyh@USTC-ACM
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).