Задача №112792. XOR
Сегодня на уроке логики Паша и Андрей узнали про новую операцию — XOR двух чисел. Напомним, что XOR или «Исключающим ИЛИ», называется бинарная операция, которая применяется к каждой паре битов, стоящих на одинаковых позициях в двоичных представлениях чисел так, что, если биты равны, то в результате на этой позиции стоит 0, если же биты различны, то 1. Например, 3 XOR 5 = 6, потому что 310 = 0112, 510 = 1012, поэтому после применения операции второй и третий бит становятся равными 1, а первый бит — 0, таким образом получается 1102 = 610.
Эта операция им так понравилась, что они придумали игру. Паша выписывает n натуральных чисел ai, затем Андрей называет m натуральных чисел bj. Затем Паша для каждого числа bj находит такое k, что результат операции bj XOR ak наибольший из возможных.
Но Паша пока не очень быстро умеет находить такие числа. Помогите Паше в этом!
Первая строка входного файла содержит одно натуральное число n (1 ≤ n ≤ 100000) — количество чисел, выписанных Пашей. Вторая строка содержит эти числа ai (0 ≤ ai ≤ 109). Все ai различны.
Третья строка входного файла содержит натуральное число m (1 ≤ m ≤ 100000) — количество чисел, названных Андреем. Четвертая строка содержит эти запросы bj (0 ≤ bj ≤ 109).
В выходной файл выведите m чисел: для каждого bj выведите такое ak, что ak XOR bj максимально.
2
0 1
2
2 3
1 0
2
3 0
3
2 3 9
0 0 3
n , m ≤ 1000 . Решение оценивается в 40 баллов.