题目描述

给定一个包含 $n$ 个非负整数的数组。

你需要回答 $q$ 个互相独立的情形。第 $i$ 个情形中，允许你最多执行 $b_i$ 次如下操作：

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

你的目标是使整个数组按位或（bitwise OR）后的结果中二进制位为 $1$ 的个数最大化。对于每个情形，求能得到的最大 $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$）——第 $i$ 个情形允许的最多操作次数。

保证所有测试用例中 $\sum n\le 10^5$ 且 $\sum q\le 10^5$。

输出格式

对于每个测试用例，输出 $q$ 行，第 $i$ 行为在第 $i$ 个情形中能得到的最多的二进制 $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

说明

样例 1 解释

• 第一个情形：不能做操作，原数组 OR 为 $0$，有 $0$ 个 $1$ 位。
• 第二个情形：允许 $2$ 次操作，把 $a_1$ 加 $1$ 两次得 $2$，二进制 $10$，有 $1$ 个 $1$ 位，是最优。
• 第三个情形：允许 $3$ 次操作，把 $a_1$ 加 $1$ 三次得 $3$，二进制 $11$，有 $2$ 个 $1$ 位，是最优。

样例 2 解释

• 第一个情形：不做操作，原数组 OR 为 $1\ |\ 3 = 3$，有 $2$ 个 $1$ 位。
• 第二个情形：允许 $3$ 次操作，可以对 $a_2$ 加 $1$ 三次使 OR 的 $1$ 位数达到 $3$。