Монети і запити
У Іри є n монет, номінал i-тої монети рівний a[i]
. Гарантується, що всі номінали є натуральними степенями числа 2, тобто a[i]
=2^d
, 0 ≤ d.
Іра хоче знати відповіді на q запитів. j - тий запит описується цілим число b[j]
. Відповіддю на запит є мінімальна кількість монет, необхідна для отримання суми b[j]
, використовуючи лише монети, які є у Іри. Якщо Іра не може отримати суму b[j]
, то відповіддю на j-тий запит буде -1.
Відповідь на запит не впливає на монети Іри.
Вхідні дані
Перший рядок містить два цілих числа n і q (1 ≤ n, q ≤ 2·10^5
) – кількість монет і кількість запитів.
Другий рядок містить n цілих чисел a[1]
,a[2]
… a[n]
(1 ≤ a[i]
≤ 2·10^9
) – номінали монети.
Наступні q рядків містять по одному числу b[j]
(1 ≤ b[j]
≤ 10^9
) – відповідний запит.
Вихідні дані
Виведіть q цілих чисел ans[j]
, j-те число повинно бути відповіддю на j-тий запит.