Water packaging
As Izina water gained fame and popularity, Izya became the leading water supplier in the country. Major corporations, institutions, and even small groups felt it was their duty to purchase water exclusively from Izya. With this growth, new challenges emerged.
Orders started coming in for extremely large quantities of water, too large to fit in any single bottle. To meet this demand, Izya hired a van to deliver water in any required amount. The only remaining question was how to measure the exact volume needed.
Fortunately, Izya had N different types of bottles, each with a specific capacity. The task now was to distribute the required volume of water for each order into bottles as efficiently as possible.
Input
The first line contains a single integer N (2 ≤ N ≤ 10) — the number of different bottle types available to Izya.
The second line lists N natural numbers a_i (1 ≤ a_i ≤ 1000) — the capacity of the i-th type of bottle. Note that different types of bottles may have the same capacity. There is an unlimited supply of each type of bottle.
The third line contains a single integer M (1 ≤ M ≤ 100000) — the number of orders Izya has received.
Each of the following M lines contains a single integer X_j (1 ≤ X_j ≤ 10^14) — the volume of water required for the j-th order.
Output
For each of the M orders, output on a separate line the minimum number of bottles needed to exactly measure X_j liters of water. If it is not possible to measure the exact volume with the available bottles, output -1.