水母和花正在玩游戏。
游戏由两个 $$$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$$$,本轮进行如下:
- 如果 $$$c_i = \mathtt{0}$$$,Gellyfish 将成为活跃玩家。否则,如果 $$$c_i = \mathtt{1}$$$,Flower 将成为活跃玩家。
- 活跃玩家将执行 正好一个 以下操作:
- 设置$$$x:=x \oplus a_i$$$。
- 设置 $$$x:=x \oplus b_i$$$。
这里,$$$\oplus$$$ 表示按位异或运算。
Gellyfish 希望在 $$$ n $$$ 轮后最小化 $$$ x $$$ 的最终值,而 Flower 希望最大化它。
如果两名玩家都发挥最佳状态,则在所有 $$$ n $$$ 轮后求 $$$ x $$$ 的最终值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 所有 $$$ n $$$ 轮后 $$$ x $$$ 的最终值。
示例
输入复制
51020212 213 31136 1 26 2 301041 12 7 24 14 4 2011190 5 10 6 6 2 6 2 117 3 15 3 6 7 6 7 8110010010
输出复制
0 15 6 11 5
注意
在第一个测试用例中,只有一轮,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$$$的最终值,所以Flower会在第二轮选择$$$b_2$$$。因此,$$$x$$$ 的最终值为$$$6$$$。