解题思路

先把式子按二进制位拆开看。

设当前考虑第 $k$ 位，权值为 $2^k$。 由于按位与、按位异或、按位或都是“逐位独立”计算的，所以这一位对总答案的贡献，只和：

• $a_i$ 的第 $k$ 位是 $0$ 还是 $1$
• $s_i$ 的类型

题目内容

天才同学给笨蛋同学留下一道小练习：给定一个长度为 $n$ 的整数序列 {$a_1,a_2,…,a_n$}，以及一个同样长度为 $n$ 的字符串 $s$，其中每个字符$s_i$ 只可能是 $1, 2, 3$之一。

你需要在区间 $[1,r]$中选择一个整数 $x$，并据此计算这个序列的"权值和"。对每个位置$i$：

• 当 $s_i=1$时，该项贡献为 $ai$&$x$
• 当$s_i=2$时，该项贡献为 $a_i⊕x$
• 当 $s_i=3$时，该项贡献为 $a_i∣x$

定义总权值为：

$W(x)=∑_{i=1}^nf(a_i,x,s_i)$

请你求出 $max_{x∈[1,r]}W(x)$ 的值。

符号$⊕$表示按位异或运算(对两个数的二进制逐位异或)对应位不同为$1$，相同为$0$。例如$5(101_2)$与$3 (011_2)$满足$5\ xor\ 3=6 (110_2)$。

符号&表示按位与运算(对两个数的二进制逐位相与)对应位都为$1$时结果为$1$，否则为$0$。例如$5(101_2)$与$3 (011_2)$满足$5\ and\ 3=1 (001_2)$

符号$|$表示按位或运算(对两个数的二进制逐位相或)对应位只要有一个为$1$结果为$1$，否则为$0$。 例如$5 (101_2)$与$3 (011_2)$满足$5\ or\ 3=7 (111_2)$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$t(1≤t≤2×10^5)$代表数据组数，每组测试数据描述如下

第一行输入两个整数$n$和$r(1≤n≤2×10^5;1≤r≤10^9)$。

第二行输入$n$个整数$a_1,a_2,...,a_n(0≤a_i≤10^9)$

第三行输入一个长度为$n$的字符串$s$，保证对所有$1≤i≤n$，都有$s_i$∈{$1,2,3$}

除此之外，保证单个测试文件的$\sum n$不超过$4×10^5$

输出描述

对于每一组测试数据，新起一行输出一个整数，表示$max_{x∈[1,r]}W(x)$

样例1

输入

3
3 7
1 2 3 
123
4 3
1 1 1 1
1111
5 10
5 6 7 8 9
23231

输出

15
4
60

说明

数组为 {$2,2,3,3,2$}。所有满足$i≠j$的有序二元组 ($i,j$) 共有 $5×4=20$ 个。其中满足 $a_i+a_j$ 为合数的二元组有：

• $a_i=2,a_j=2$：和为 $2+2=4$（合数）。由于数组中有 $3$个 $2$，可以组成$3×2=6$ 个这样的有序对。
• $a_i=3,a_j=3$：和为 $3+3=6$（合数）。由于数组中有$2$ 个$3$，可以组成 $2×1=2$个这样的有序对。

总计 $6+2=8$个。