High Load Database#9525
Henry profiles a high load database migration script. The script is the list of transactions. The -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 .
Unfortunately, Henry does not know the exact value of for the production database, so he is going to estimate the minimum number of batches for possible values of : t_1, t_2, \ldots, t_q. Help Henry to calculate the number of transactions for each of them.
The first line contains the number of transactions (1 \le n \le 200\,000) in the migration script.
The second line consists of integers a_1, a_2, \ldots, a_n - the number of queries in each transaction (1 \le a_i; \sum a_i \le 10^6).
The third line contains the number of queries (1 \le q \le 10^5).
The fourth line contains integers t_1, t_2, \ldots, t_q (1 \le t_i \le \sum a_i).
Print lines. The -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.
Example 1