UOJ Logo

NOI.AC

2S 64MB

#715. 异或

Statistics

时间:2秒 空间:64MB

题目描述

输入3个数组,每个数组中含有n个小于32768的整数,其中可能含有重复的元素。

你需要得出一个数组A,表示从3个数组中分别选取一个元素,得到的3个整数的异或结果。显然,A中有$n^3$个元素。

由于A数组可能太长,不需要你将其所有元素输出。我们只输入q个询问,每次输入一个k,问你数组A中第k小的元素是几。

(提示:在C/C++语言中你可以使用a^b^c计算三个数的异或)

输入格式

第一行输入两个整数n和q。

第二行到第四行,每行输入n个整数,分别表示3个数组。

接下来q行,每行输入一个整数,表示此次询问的k。

输出格式

对于每个询问输出一行,包含一个整数,表示该询问的答案。

样例输入

3 5
1 2 3
2 2 3
3 2 3
2
8
14
20
26

样例输出

0
1
2
3
3

数据范围

保证q≤50,对于每个询问保证1≤k≤$n^3$

除样例外,输入的每个数组的每个元素与每一个询问都是独立、均匀随机生成的。

25个测试点的n分别为:

 1  35 200 1000  5000
10  50 250 1500  7000
15  70 350 2000 10000
20 100 500 2500 15000
25 150 700 3500 20000