19 · Eating · GESP考级

题目描述

有 $n$ 个史莱姆排成一行，第 $i$ 个史莱姆的体重为 $w_i$。当史莱姆 $i$ 满足 $w_i \geq w_j$ 时，它可以吃掉史莱姆 $j$；之后，史莱姆 $j$ 会消失，史莱姆 $i$ 的体重将变为 $w_i \oplus w_j$ $^{\text{∗}}$。 史莱姆国王希望进行一个参数为 $x$ 的实验，步骤如下： 在行的最右端（第 $n$ 个史莱姆之后）新增一个体重为 $x$ 的史莱姆。 这个新史莱姆会不断尝试吃掉左侧相邻的史莱姆（如果可能的话），并移动到被吃掉的史莱姆的位置。当左侧没有史莱姆或其左侧史莱姆的体重大于自身时，该过程停止。（此过程中不会有其他史莱姆被吃掉） 该实验的得分为被吃掉的史莱姆总数。 史莱姆国王将向你提出 $q$ 次询问。每次询问给定一个整数 $x$，你需要计算以该参数进行实验的得分。 注意这些询问是假设性的，并不会实际改变史莱姆的初始状态（即查询是非持久化的）。 $^{\text{∗}}$ 此处 $\oplus$ 表示按位异或运算。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例数量。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）——分别表示初始史莱姆数量和询问次数。 接下来一行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$（$1 \le w_i 2^{30}$）——初始史莱姆的体重。 接下来 $q$ 行每行包含一个整数 $x$（$1 \le x 2^{30}$）——实验参数。 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，$q$ 之和不超过 $2 \cdot 10^5$。

对于每个询问，输出一个整数表示实验得分。

输入 #1

3
1 1
5
6
4 4
1 5 4 11
8
13
16
15
10 9
10 4 3 9 7 4 6 1 9 4
2
6
5
6
9
8
6
2
7

输出 #1