Coins and Queries#8782
Ira has a collection of coins, each with a denomination represented by a_i. It is guaranteed that each denomination is a natural power of 2, meaning a_i = 2^d, where 0 \le d.
Ira needs to answer queries. Each query is defined by an integer b_j. The task is to determine the minimum number of coins required to achieve the sum b_j using Ira's coins. If it is not possible to form the sum b_j, the answer for that query should be .
Note that answering a query does not alter the collection of coins Ira possesses.
The first line contains two integers and (1 \le n, q \le 2 \cdot 10^5) – representing the number of coins and the number of queries, respectively.
The second line lists integers a_1, a_2, \ldots, a_n (1 \le a_i \le 2 \cdot 10^9) – these are the denominations of the coins.
The following lines each contain a single integer b_j (1 \le b_j \le 10^9) – representing each query.
Output integers ans_j, where the -th integer is the answer to the -th query.
Example 1