← 返回题目列表

Codeforces · 2008/H

H. 樱子的测试

中文机器翻译题面 查看原题

樱子很快就要考试了。该测试可以描述为一个整数数组 $$$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