Timur 有 $$$n$$$ 糖果。第 $$$i$$$ 糖果的糖含量等于 $$$a_i$$$。因此,通过吃第 $$$i$$$ 糖果,Timur 消耗的糖量等于 $$$a_i$$$。
Timur 会询问你关于他的糖果的 $$$q$$$ 问题。对于第 $$$j$$$ 查询,您必须回答他需要吃的最小糖果数量是多少,才能达到大于或等于 $$$x_j$$$ 的糖量,如果无法获得这样的数量,则打印 -1。换句话说,您应该打印最小可能的 $$$k$$$,这样在吃完 $$$k$$$ 糖果后,Timur 消耗的糖量至少为 $$$x_j$$$,或者说不存在可能的 $$$k$$$。
请注意,他不能吃两次相同的糖果,并且查询是相互独立的(Timur 可以在不同的查询中使用相同的糖果)。
输入
输入的第一行包含一个整数 $$$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$$$ 行输出,Timur 需要吃多少糖果才能达到大于或等于 $$$x_j$$$ 的糖量,如果无法获得这样的数量,则打印 -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 可以吃任何糖果,并且他会达到所需的数量。
对于第二个查询,Timur 通过吃第 $$$7$$$ 和第 $$$8$$$ 糖果可以达到至少 $$$10$$$ 的数量,从而消耗相当于 $$$14$$$ 的糖量。
对于第三个查询,没有可能的答案。
对于第四个查询,Timur 通过吃第 $$$7$$$ 和第 $$$8$$$ 糖果可以达到至少 $$$14$$$ 的数量,从而消耗等于 $$$14$$$ 的糖量。
对于第二个测试用例:
对于第二个测试用例的唯一查询,我们可以选择 Timur 从中恰好收到 $$$3$$$ 糖的第三颗糖果。选择第四颗糖果也可以获得相同的答案。