题目内容

在通信系统测试中，工程师设置了一条包含 $n$ 个信号节点的链路，每个节点 $i$ 有一个基准功率 $A_i$ 和一个操作码 $P_i$（可能为 '1'、'2' 或 '3'）。系统允许引入一个调试参数 $x$，且 $x$ 必须从区间 $[1, r]$ 中选取。

对于每一个节点 $i$，根据操作码 $P_i$ 会按以下方式计算一个叠加功率：

• 若 $P_i =$ '1'，则叠加功率为 $A_i \& x$（按位与：二进制对应位均为 1 时结果位为 1，否则为 0）；
• 若 $P_i =$ '2'，则叠加功率为 $A_i \oplus x$（按位异或：二进制对应位不同则结果位为 1，相同则为 0）；
• 若 $P_i =$ '3'，则叠加功率为 $A_i | x$（按位或：二进制对应位只要有一个为 1 结果位即为 1）。

整个链路的总叠加功率定义为：

你的任务是选择一个合适的 $x$（$1 \le x \le r$），使得总叠加功率 $V(x)$ 最大化，并输出这个最大值。

数据规模：

• 测试数据组数 $t$ 不超过 2×10^5；
• 每组数据中，节点个数 $n$ 不超过 2×10^5，参数上限 $r$ 不超过 10^9；
• 基准功率 $A_i$ 均为非负整数，且不超过 10^9；
• 所有测试数据的 $n$ 总和不超过 4×10^5；
• 操作码字符串长度等于 $n$，且仅由字符 '1'、'2'、'3' 构成。

输入描述

第一行输入一个整数 $t$，表示测试数据组数。 接下来每组数据按以下格式给出： 第一行包含两个整数 $n$ 和 $r$，分别表示节点个数和参数上限。 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示各节点的基准功率。 第三行包含一个长度为 $n$ 的字符串，仅由字符 '1'、'2'、'3' 组成，依次表示每个节点的操作码。

输出描述

对于每组测试数据，输出一行一个整数，表示能达到的最大总叠加功率 $\max_{1 \le x \le r} V(x)$。

样例1

输入

1
1 5
3
1

输出

3

说明

只有一个节点，基准功率 $A_1 = 3$，操作码为 '1'（按位与），参数上限 $r = 5$。$x$ 只能在区间 $[1, 5]$ 中选取。计算不同 $x$ 的叠加功率：

• $x = 3$：$3 \& 3 = 3$；
• $x = 5$：$3 \& 5 = 1$。 其他取值叠加功率均不超过 3，因此最大总叠加功率为 3。

样例2

输入

1
2 6
2 4
23

输出

12

说明

两个节点，基准功率分别为 2 和 4，操作码依次为 '2'（按位异或）和 '3'（按位或），上限 $r = 6$。 考虑每个比特位的贡献。可以验证 $x = 5$ 时总叠加功率最大：

• 节点 1：$2 \oplus 5 = 7$；
• 节点 2：$4 \mid 5 = 5$；
• 总叠加功率 $V(5) = 7 + 5 = 12$。 在 $1 \le x \le 6$ 范围内，$x = 5$ 取得最大值 12。

样例3

输入

1
3 8
5 7 6
321

输出

28

说明

三个节点，基准功率依次为 5、7、6，操作码依次为 '3'（按位或）、'2'（按位异或）、'1'（按位与），上限 $r = 8$。 通过分析各比特位贡献，取 $x = 8$ 可获得最大总和：

• 节点 1：$5 \mid 8 = 13$；
• 节点 2：$7 \oplus 8 = 15$；
• 节点 3：$6 \& 8 = 0$；
• 总和 $V(8) = 13 + 15 + 0 = 28$。 其余 $x \in [1, 8]$ 均无法超越该值，故最大值为 28。

样例4

输入

1
1 1
0
1

输出

0

说明

只有一个节点，基准功率 $A_1 = 0$，操作码为 '1'（按位与），上限 $r = 1$。$x$ 只能取 1。叠加功率为 $0 \& 1 = 0$，因此最大值为 0。该样例展示了在必须选择 $x \ge 1$ 的前提下，最大值可能为 0。