【题目描述】
提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。
C城是一座魔力之都，以最高的魔法师水平闻名。对于一名魔法师而言，最重要的固然是魔法手杖和镶嵌在手杖上的魔法水晶。
每个魔法手杖和魔法水晶都可以用魔力值来衡量其能力大小，一个魔法手杖的魔力值是镶嵌在其上的所有魔法水晶中魔力值的最小值。
小ω是C城的一名见习魔法师，他想加强他的魔法手杖。在加强之前，小ω的魔法手杖镶嵌着n颗魔法水晶，它们的魔力值分别为$a_1,a_2,···,a_n$。
小ω准备使用一次强力的秘术来加强他的手杖。这一次秘术中，他可以任意选择x，然后将所有魔法水晶的魔力值由ai变为(ai⊕x)，其中⊕表示按位异或。由于小ω能力有限，$a_1,a_2,···,a_n$和x都是$[0,2^k−1]$中的整数。
小ω还发现这个秘术可以定向加强。具体地，他可以花费bi的体力值对第i个魔法水晶进行定向加强，将原本应变为$(a_i⊕x)$的魔力值变为$(a_i+x)$。小ω能力有限，因此他定向加强所花费的体力值总和不能超过m，且每个水晶只能被定向加强至多一次。
小ω想知道他在加强魔法手杖后，魔法手杖的魔力值最大能为多少，但他并不会算，所以请你来帮他计算。
形式化的：给定$a_1,a_2,···,a_n$以及$b_1,b_2,···,b_n$，满足$ai∈[0,2^k−1]$以及$b_i≥0$，你需要给出$S⊆{1,2,···,n}$以及$x∈[0,2^k−1]$满足以下条件：

•$\sum_{i∈S}b_i≤m$；
•满足以上条件的前提下，最大化的值。
你只需要给出最大的$val(S,x)$的值即可。

本题有多组测试数据。输入的第一行包含两个整数c,T，表示测试点编号与测试数据组数。样例中的c表示该样例的数据范围与第c个测试点的数据范围相同。
接下来依次给出每组输入数据，对于每组数据：
•第一行三个整数$n,m,k$；
•第二行$n$个整数$a_1,a_2,···,a_n$，分别表示每个魔法水晶的初始魔力值；
•第三行$n$个整数$b_1,b_2,···,b_n$，分别表示每个魔法水晶定向加强需要的体力值。

对于每组测试数据输出一行一个整数表示小ω能获得魔法手杖魔力值的最大值。

【样例 1 解释】
•对于第一组数据，一种可行的方案为：定向强化魔法水晶5（即S={5}）并取x=4。最后得到的魔法水晶魔力值分别为5,5,6,7,11，故魔法手杖的魔力值为5。可以证明不存在更优方案。
•对于第二组数据，一种可行的方案为：定向强化魔法水晶1（即S={1}）并取x=1。
【样例2】
该组样例满足c=4。
【样例3】
该组样例满足c=7。
【样例4】
该组样例满足c=9。
【样例5】
该组样例满足c=11。
【样例6】
该组样例满足c=14。
【样例7】
该组样例满足c=22。
【子任务】
设$\sum n$表示单组测试点各组数据n的和。对于所有测试数据，
• $T ≥ 1$；
• $1 ≤ n ≤ 10^5，1 ≤ ∑n ≤ 5 × 10^5$；
• $0 ≤ m ≤ 10^9$；
• $0 ≤ k ≤ 120$；
• $∀1 ≤ i ≤ n，0 ≤ a_i < 2^k$；
• $∀1 ≤ i ≤ n，0 ≤ b_i ≤ 10^9$。

特殊性质 A：$m = 0；∀1 ≤ i ≤ n，b_i ≥ 1$。
特殊性质 B：$m = 1；∀1 ≤ i ≤ n，b_i ∈ {1, 2}$，且至多只有1个$i$满足$b_i = 1$。
特殊性质 C：$m = 1；∀1 ≤ i ≤ n，b_i ∈ {1, 2}$。
【提示】
本题输入文件较大，请使用较为快速的输入方式。
在评测环境中，你可以使用128位有符号整型类型__int128，它可以存储范围在$[−2^{127},2^{127−1}]$内的整数，使用方法与其他整型类型基本一致。
需要注意，该类型无法使用诸如cin/cout或scanf/printf等常规输入输出方式进行输入输出。我们在选手目录下提供了一份__int128的输入输出函数实现供选手选择使用。