Областная олимпиада по информатике 2017 г.

Хром очень любит шоколадки. У него есть шоколадка Everest Silver размером $1$ x $n$. На каждом кусочке шоколада написано число $a_i$. Вкусность плитки определяется xor-суммой по числам на её кусочках. Хром хочет съесть весь шоколад. Он может съедать по одному кусочку шоколада в определенном порядке. После каждого съеденного кусочка плитка, которой принадлежал кусочек, поделится на два. Хром хочет знать максимальную вкусность среди оставшихся плиток шоколада после каждого съеденного кусочка. Так как он очень спешит, он просит вас помочь ему.

Входные данные

В первой строке находится целое положительное число $n (1 ≤ n ≤ 10^5)$ - длина шоколада. Во второй строке находятся n чисел $a_i (1 ≤ a_i ≤ 10^9)$. В последней строке находятся $n$ целых положительных чисел $x (1 ≤ x ≤ n)$ - номер очередного съеденного кусочка.

Выходные данные

Выведите $n$ чисел - наибольшую вкусность по всем плиткам.

Система оценки

В 24% тестов: $1 ≤ n ≤ 1000$.
В 16% тестов: В порядке будут задаваться сперва нечетные в порядке возрастания, а затем четные в порядке возрастания, второй пример соответствует данному условию, $1 ≤ n ≤ 10^5$.

Примеры:

1. Вход:

5 
1 2 5 4 3 
2 4 1 3 5

Ответ:

2 5 5 3 0

2. Вход:

5 
1 2 5 4 3 
1 3 5 2 4

Ответ:

0 7 4 4 0

Примечание:

Изначально шоколад состоит из 5 кусков: [1, 2, 5, 4, 3].
После съедания первого кусочка шоколад поделился на 2 плитки: [1], [5, 4, 3].
Наибольшая вкусность равняется 2 потому что xor-сумма первой плитки равняется - 1, xor-сумма второй равняется 5 xor 4 xor 3 = 2, из них наибольшее - 2.
После исчезновения второго кусочка шоколад поделился на 3 плитки: [1], [5], [3]
Наибольшая вкусность равняется 5.
Побитовое исключающее ИЛИ (xor) — это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичной записи операндов. Иными словами, если соответствующие биты операндов различны, то соответствующий двоичный разряд результата равен 1; если же биты одинаковые, то двоичный разряд результата равен 0.
Например, если $X = 109_{10} = 1101101_2$, $Y = 41_{10} = 101001_2$ тогда: $X$ xor $Y$ = $68_{10}$ = $1000100_2$. Xor-суммой последовательности называется $xor$ всех элементов последовательности — $a_1 xor a_2 xor ... xor a_{n−1} xor a_n$.