E. Запросы на поедание конфет
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Тимура есть $$$n$$$ конфет. В $$$i$$$-й конфете количество сахара равно $$$a_i$$$. Так, съев $$$i$$$-ю конфету, Тимур потребляет количество сахара, равное $$$a_i$$$.

Тимур задаст вам $$$q$$$ запросов о своих конфетах. Для $$$j$$$-го запроса вы должны ответить, какое минимальное количество конфет ему нужно съесть, чтобы потребить количество сахара, большее или равное $$$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$$$) — количество конфет, которые есть у Тимура и количество запросов соответственно.

Вторая строка каждого набора содержит $$$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$$$) — количество сахара, которое хочет получить Тимур.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$1.5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ строк. В $$$j$$$-й строке выведите количество конфет, которое нужно съесть Тимуру, чтобы получить количество сахара, большее или равное $$$x_j$$$. Выведите -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
2
-1
2
3
4
8
1
1
-1
Примечание

В первом наборе входных данных примера:

  • В первом запросе Тимур может съесть любую конфету, и он наберет нужное количество.
  • Во втором запросе Тимур может получить количество не менее $$$10$$$, съев $$$7$$$-ю и $$$8$$$-ю конфету, таким образом потребив количество сахара, равное $$$14$$$.
  • На третий запрос нет возможного ответа.
  • В четвертом запросе Тимур может получить количество как минимум $$$14$$$, съев $$$7$$$-ю и $$$8$$$-ю конфету, таким образом потребив количество сахара, равное $$$14$$$.

Во втором наборе входных данных примера:

  • Для единственного запроса второго набора входных данных мы можем выбрать третью конфету, из которой Тимур получает количество сахара равное $$$3$$$. Также можно получить тот же ответ, выбрав четвертую конфету.