E. 最大或 Popcount

每次测试时间限制： $2$ 秒
每次测试内存限制： $256$ 兆字节

你有一个由 $n$ 个非负整数组成的数组。

你需要回答 $q$ 个独立的询问。在第 $i$ 个询问中，你最多可以执行 $b_i$ 次操作：

• 选择数组中的一个元素，将其增加 $1$。

你的目标是最大化整个数组按位或（bitwise OR）结果中二进制表示中 $1$ 的个数。
对每个询问，输出这个最大值。

输入

每个测试点包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。

每个测试用例：

• 第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$）——数组大小和询问数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）。
• 接下来 $q$ 行，每行一个整数 $b_i$（$0 \le b_i \le 10^9$），表示该询问允许的最大操作次数。

保证所有测试用例的 $n$ 之和不超过 $10^5$，所有测试用例的 $q$ 之和不超过 $10^5$。

输出

对于每个测试用例，输出 $q$ 行，第 $i$ 行包含一个整数——在第 $i$ 个询问中，通过最多 $b_i$ 次加 $1$ 操作后，能得到的按位或结果中二进制 $1$ 的最大个数。

示例

输入：

3
1 3
0
0
2
4
2 2
1 3
0
3
2 1
1000000000 1000000000
1000000000

输出：

0
1
2
2
3
31

注释

第一个测试用例（$n=1, a=[0]$）：

• 询问 $1$：$b=0$，不能操作，按位或为 $0$，二进制 $1$ 的个数 = $0$。
• 询问 $2$：$b=2$，可以加 $1$ 两次：$0 \to 1 \to 2$，按位或为 $2 = (10)_2$，有 $1$ 个 $1$。
• 询问 $3$：$b=4$，加 $1$ 三次：$0 \to 1 \to 2 \to 3$，按位或为 $3 = (11)_2$，有 $2$ 个 $1$。

第二个测试用例（$n=2, a=[1,3]$）：

• 询问 $1$：$b=0$，原数组按位或 $1 | 3 = 3 = (11)_2$，有 $2$ 个 $1$。
• 询问 $2$：$b=3$，可以对 $a_2=3$ 加 $1$ 三次：$3 \to 4 \to 5 \to 6$，此时 $a=[1,6]$，按位或 $1|6=7=(111)_2$，有 $3$ 个 $1$。

第三个测试用例（$n=2, a=[10^9,10^9]$）：

• 询问 $1$：$b=10^9$，可以将其中一个 $10^9$ 加到 $2\times10^9$ 附近，最优结果是 $31$ 个 $1$（因为 $2^{31}-1$ 约 $2.147\times10^9$，在 $10^9$ 次操作内可达）。