樱子很快就要考试了。该测试可以描述为一个整数数组 $$$n$$$ 和一个关于它的任务:
给定一个整数 $$$x$$$,Sakurako 可以执行以下操作任意次:
- 选择一个整数 $$$i$$$ ($$$1\le i\le n$$$) 使得 $$$a_i\ge x$$$;
- 将 $$$a_i$$$ 的值更改为 $$$a_i-x$$$。
使用此操作任意多次,她必须找到数组$$$a$$$ 的最小可能中位数$$$^{\text{*}}$$$。
Sakurako 知道数组,但不知道整数 $$$x$$$。有人无意中透露,$$$x$$$ 的 $$$q$$$ 值之一将出现在下一次测试中,因此 Sakurako 正在问您每个这样的 $$$x$$$ 的答案是什么。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\le n,q\le 10^5$$$) — 数组中的元素数量和查询数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le n$$$) — 数组的元素。
以下 $$$q$$$ 行每行包含一个整数 $$$x$$$ ($$$1\le x\le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。同样的保证适用于所有测试用例的 $$$q$$$ 总和。
输出
对于每个测试用例,输出 $$$q$$$ 整数 - 每个查询的答案。
示例
输入 #1
2 5 5 1 2 3 4 5 1 2 3 4 5 6 3 1 2 6 4 1 3 2 1 5
输出 #1
0 1 1 1 2 1 0 2