У Тимура есть \(n\) конфет. В \(i\)-й конфете количество сахара равно \(a_i\). Так, съев \(i\)-ю конфету, Тимур потребляет количество сахара, равное \(a_i\).
Тимур задаст вам \(q\) запросов о своих конфетах. Для \(j\)-го запроса вы должны ответить, какое минимальное количество конфет ему нужно съесть, чтобы потребить количество сахара, большее или равное \(x_j\). Выведите -1, если невозможно получить такое количество. Другими словами, нужно вывести минимально возможное \(k\) такое, что, съев \(k\) конфет, Тимур получит количество сахара не менее \(x_j\), или сказать, что такого \(k\) не существует.
Обратите внимание, что он не может съесть одну и ту же конфету дважды, а запросы не зависят друг от друга (Тимур может использовать одну и ту же конфету в разных запросах).
Выходные данные
Для каждого набора входных данных выведите \(q\) строк. В \(j\)-й строке выведите количество конфет, которое нужно съесть Тимуру, чтобы получить количество сахара, большее или равное \(x_j\). Выведите -1, если получить такое количество невозможно.
Примечание
В первом наборе входных данных примера:
- В первом запросе Тимур может съесть любую конфету, и он наберет нужное количество.
- Во втором запросе Тимур может получить количество не менее \(10\), съев \(7\)-ю и \(8\)-ю конфету, таким образом потребив количество сахара, равное \(14\).
- На третий запрос нет возможного ответа.
- В четвертом запросе Тимур может получить количество как минимум \(14\), съев \(7\)-ю и \(8\)-ю конфету, таким образом потребив количество сахара, равное \(14\).
Во втором наборе входных данных примера:
- Для единственного запроса второго набора входных данных мы можем выбрать третью конфету, из которой Тимур получает количество сахара равное \(3\). Также можно получить тот же ответ, выбрав четвертую конфету.
Примеры
| № | Входные данные | Выходные данные |
|
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
|