CF2115D.Gellyfish and Forget-Me-Not

Gellyfish and Flower are playing a game.

The game consists of two arrays of $n$ integers $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$, along with a binary string $c_1c_2\ldots c_n$ of length $n$.

There is also an integer $x$ which is initialized to $0$.

The game consists of $n$ rounds. For $i = 1,2,\ldots,n$, the round proceeds as follows:

1. If $c_i = \mathtt{0}$, Gellyfish will be the active player. Otherwise, if $c_i = \mathtt{1}$, Flower will be the active player.
2. The active player will perform exactly one of the following operations:
   • Set $x:=x \oplus a_i$.
   • Set $x:=x \oplus b_i$.

Here, $\oplus$ denotes the bitwise XOR operation.

Gellyfish wants to minimize the final value of $ x $ after $ n $ rounds, while Flower wants to maximize it.

Find the final value of $ x $ after all $ n $ rounds if both players play optimally.

水母和花朵正在玩一个游戏。

游戏包含两个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$ 和 $b_1,b_2,\ldots,b_n$，以及一个长度为 $n$ 的二进制字符串 $c_1c_2\ldots c_n$。

此外还有一个整数 $x$，初始值为 $0$。

游戏共进行 $n$ 轮。对 $i = 1,2,\ldots,n$，第 $i$ 轮按如下方式进行：

1. 若 $c_i = \mathtt{0}$，则水母为当前活跃玩家；若 $c_i = \mathtt{1}$，则花朵为当前活跃玩家。
2. 当前活跃玩家恰好执行以下操作之一：
   • 将 $x$ 更新为 $x:=x \oplus a_i$；
   • 将 $x$ 更新为 $x:=x \oplus b_i$。

其中，$\oplus$ 表示按位异或运算。

水母希望在 $n$ 轮结束后使 $x$ 的最终值尽可能小，而花朵希望使其尽可能大。

若双方均采取最优策略，求 $n$ 轮结束后 $x$ 的最终值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of rounds of the game.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 2^{60}$).

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \lt 2^{60}$).

The fourth line of each test case contains a binary string $c$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$）。

每个测试用例的第四行包含一个长度为 $n$ 的二进制字符串 $c$。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, output a single integer — the final value of $ x $ after all $ n $ rounds.

对于每个测试用例，输出一个整数——经过全部 $ n $ 轮操作后 $ x $ 的最终值。

In the first test case, there's only one round and Gellyfish is the active player of that round. Therefore, she will choose $a_1$, and the final value of $x$ is $0$.

In the second test case, Flower will be the active player in both rounds. She will choose $a_1$ and $b_2$, and the final value of $x$ is $a_1 \oplus b_2 = 15$. Flower may also choose $b_1$ and $a_2$ instead for the same result of $x=a_2 \oplus b_1 = 15$.

In the third test case, $a_1 = b_1$ so it doesn't matter what decision Gellyfish makes in the first round. In the second round:

• If Flower chooses $a_2$, then $x$ will become $7$. Gellyfish will choose $b_3$ in the third round, so the final value of $x$ will be $4$.
• Otherwise, Flower chooses $b_2$, then $x$ will become $4$. Gellyfish will choose $a_3$ in the third round, so the final value of $x$ will be $6$.

Flower wants to maximize the final value of $x$, so Flower will choose $b_2$ in the second round. Therefore, the final value of $x$ will be $6$.

在第一个测试用例中，仅有一轮，且 Gellyfish 是该轮的活跃玩家。因此，她将选择 $a_1$，最终 $x$ 的值为 $0$。

在第二个测试用例中，Flower 将在两轮中均为活跃玩家。她将选择 $a_1$ 和 $b_2$，最终 $x$ 的值为 $a_1 \oplus b_2 = 15$。Flower 也可改为选择 $b_1$ 和 $a_2$，此时同样得到 $x = a_2 \oplus b_1 = 15$。

在第三个测试用例中，$a_1 = b_1$，因此 Gellyfish 在第一轮中的选择无关紧要。在第二轮中：

• 若 Flower 选择 $a_2$，则 $x$ 将变为 $7$；Gellyfish 在第三轮中将选择 $b_3$，因此 $x$ 的最终值为 $4$。
• 否则，Flower 选择 $b_2$，则 $x$ 将变为 $4$；Gellyfish 在第三轮中将选择 $a_3$，因此 $x$ 的最终值为 $6$。

Flower 希望最大化 $x$ 的最终值，因此她在第二轮中会选择 $b_2$。故 $x$ 的最终值为 $6$。