饮食查询

题目描述

帖木儿有 $n$ 颗糖果。 $i$ -th糖果的糖量等于 $a_i$ 。因此，通过吃第 $i$ 颗糖果，帖木儿消耗的糖的数量等于 $a_i$ 。

帖木儿会就他的糖果向你提出 $q$ 个问题。对于 $j$ -th个问题，您必须回答他需要吃多少颗糖果才能达到大于或等于 $x_j$ 的糖量，如果不可能达到这样的糖量，则打印-1。换句话说，你应该打印最小可能的 $k$ ，这样在吃了 $k$ 颗糖果后，铁木尔消耗的糖量至少为 $x_j$ ，或者说不存在可能的 $k$ 。

请注意，他不能两次吃同一种糖果，而且查询是相互独立的（帖木儿可以在不同的查询中使用同一种糖果）。

输入格式

第一行输入包含一个整数 $t$ ( $1 \leq t \leq 1000$ )--测试用例数。测试用例说明如下。

第一行包含 $2$ 个整数 $n$ 和 $q$ ( $1 \leq n, q \leq 1.5\cdot10^5$ )--分别是 Timur 拥有的糖果数量和需要打印答案的查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \leq a_i \leq 10^4$ ) --分别是每颗糖果中糖的数量。

接下来是 $q$ 行。

接下来的 $q$ 行中每一行都包含一个整数 $x_j$ ( $1 \leq x_j \leq 2 \cdot 10^9$ ) - 即 Timur 想要达到的给定查询量。

保证所有测试用例中 $n$ 和 $q$ 的总和不超过 $1.5 \cdot 10^5$ 。

输出格式

对每个测试用例输出 $q$ 行。对于 $j$ -th 行，输出 Timur 需要吃多少颗糖果才能使糖的数量大于或等于 $x_j$ ，如果不可能获得这样的数量，则打印 -1。

样例 #1

样例输入 #1

3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6

样例输出 #1

1
2
-1
2
3
4
8
1
1
-1

提示

对于第一个测试案例：

对于第一个查询，Timur 可以吃任何糖果，并且他将达到所需的数量。

对于第二个查询，铁木尔可以通过吃掉 $7$ -th和 $8$ -th两颗糖果来达到至少 $10$ 的数量，因此消耗的糖的数量等于 $14$ 。

对于第三个问题，没有可能的答案。

对于第四个问题，铁木尔可以通过吃 $7$ th和 $8$ th的糖果达到至少 $14$ 的数量，因此消耗的糖的数量等于 $14$ 。

第二个测试案例

对于第二个测试用例的唯一查询，我们可以选择第三颗糖果，这样铁木尔就可以从中得到恰好 $3$ 的糖。选择第四种糖果也可以得到相同的答案。