D. Гелифиш и незабудка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Гелифиш и Флауэр играют в игру.

Игра состоит из двух массивов из $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ и $$$b_1,b_2,\ldots,b_n$$$, а также бинарной строки $$$c_1c_2\ldots c_n$$$ длиной $$$n$$$.

Также есть целое число $$$x$$$, которое инициализируется значением $$$0$$$.

Игра состоит из $$$n$$$ раундов. Для $$$i = 1,2,\ldots,n$$$ раунд проходит следующим образом:

  1. Если $$$c_i = \mathtt{0}$$$, активным игроком будет Гелифиш. В противном случае, если $$$c_i = \mathtt{1}$$$, активным игроком будет Флауэр.
  2. Активный игрок выполнит ровно одну из следующих операций:
    • Присвоить $$$x:=x \oplus a_i$$$.
    • Присвоить $$$x:=x \oplus b_i$$$.

Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Гелифиш хочет минимизировать итоговое значение $$$ x $$$ после $$$ n $$$ раундов, в то время как Флауэр хочет максимизировать его.

Найдите итоговое значение $$$ x $$$ после всех $$$ n $$$ раундов, если оба игрока играют оптимально.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество раундов игры.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \lt 2^{60}$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \lt 2^{60}$$$).

Четвертая строка каждого набора входных данных содержит бинарную строку $$$c$$$ длиной $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — итоговое значение $$$ x $$$ после всех $$$ n $$$ раундов.

Пример
Входные данные
5
1
0
2
0
2
12 2
13 3
11
3
6 1 2
6 2 3
010
4
1 12 7 2
4 14 4 2
0111
9
0 5 10 6 6 2 6 2 11
7 3 15 3 6 7 6 7 8
110010010
Выходные данные
0
15
6
11
5
Примечание

В первом наборе входных данных только один раунд, и Гелифиш является активным игроком этого раунда. Поэтому она выберет $$$a_1$$$, и конечное значение $$$x$$$ будет $$$0$$$.

Во втором наборе входных данных Флауэр будет активным игроком в обоих раундах. Она выберет $$$a_1$$$ и $$$b_2$$$, и конечное значение $$$x$$$ будет $$$a_1 \oplus b_2 = 15$$$. Альтернативно, Флауэр может выбрать $$$b_1$$$ и $$$a_2$$$ для того же результата $$$x=a_2 \oplus b_1 = 15$$$.

В третьем наборе входных данных $$$a_1 = b_1$$$, поэтому не имеет значения, какое решение примет Гелифиш в первом раунде. Во втором раунде:

  • Если Флауэр выберет $$$a_2$$$, то $$$x$$$ станет $$$7$$$. Гелифиш выберет $$$b_3$$$ в третьем раунде, поэтому конечное значение $$$x$$$ будет $$$4$$$.
  • В противном случае Флауэр выберет $$$b_2$$$, тогда $$$x$$$ станет $$$4$$$. Гелифиш выберет $$$a_3$$$ в третьем раунде, поэтому конечное значение $$$x$$$ будет $$$6$$$.

Флауэр хочет максимизировать конечное значение $$$x$$$, поэтому Флауэр выберет $$$b_2$$$ во втором раунде. Таким образом, конечное значение $$$x$$$ будет $$$6$$$.