High Load Database
Henry profiles a high load database migration script. The script is the list of n transactions. The i-th transaction consists of a[i] queries. Henry wants to split the script to the minimum possible number of batches, where each batch contains either one transaction or a sequence of consecutive transactions, and the total number of queries in each batch does not exceed t.
Unfortunately, Henry does not know the exact value of t for the production database, so he is going to estimate the minimum number of batches for q possible values of t: t[1], t[2], . . . , t[q]. Help Henry to calculate the number of transactions for each of them.
Input
The first line contains the number of transactions n (1 ≤ n ≤ 200 000) in the migration script.
The second line consists of n integers a[1], a[2], . . . , a[n] - the number of queries in each transaction (1 ≤ a[i]; Σ a[i] ≤ 10^6).
The third line contains the number of queries q (1 ≤ q ≤ 10^5).
The fourth line contains q integers t[1], t[2], . . . , t[q] (1 ≤ t[i] ≤ Σ a[i]).
Output
Print q lines. The i-th line should contain the minimum possible number of batches, having at most t[i] queries each. If it is not possible to split the script into the batches for some t[i], output "Impossible" instead.
Remember that you may not rearrange transactions, only group consecutive transactions in a batch.