У Поликарпа есть \(n\) монет, достоинство \(i\)-й монеты равно \(a_i\). Гарантируется, что все достоинства являются натуральными степенями \(2\) (то есть \(a_i = 2^d\) для некоторого неотрицательного целого числа \(d\)).
Поликарп хочет знать ответы на \(q\) запросов. \(j\)-й описывается целым числом \(b_j\). Ответом на запрос является минимальное количество монет, необходимое для получения суммы \(b_j\), используя некоторое подмножество монет (Поликарп может использовать только те монеты, которые у него есть). Если Поликарп не может получить значение \(b_j\), то ответ на \(j\)-й запрос равен -1.
Запросы независимы (ответ на запрос не влияет на монеты Поликарпа).
Выходные данные
Выведите \(q\) целых чисел \(ans_j\). \(j\)-е число должно равняться ответу на \(j\)-й запрос. Если Поликарп не может получить значение \(b_j\), ответ на \(j\)-й запрос равен -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
2 4 8 2 4
8
5
14
10
|
1
-1
3
2
|