e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ACM NEERC 2019

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 ai 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: t1, t2, . . . , tq. Help Henry to calculate the number of transactions for each of them.

Input

The first line contains the number of transactions n (1n200 000) in the migration script.

The second line consists of n integers a1, a2, . . . , an - the number of queries in each transaction (1ai; Σ ai106).

The third line contains the number of queries q (1q105).

The fourth line contains q integers t1, t2, . . . , tq (1ti ≤ Σ ai).

Output

Print q lines. The i-th line should contain the minimum possible number of batches, having at most ti queries each. If it is not possible to split the script into the batches for some ti, output "Impossible" instead.

Remember that you may not rearrange transactions, only group consecutive transactions in a batch.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
4 2 3 1 3 4
8
10 2 5 4 6 7 8 8
Output example #1
2
Impossible
4
5
4
3
3
3
Source 2019 ACM NEERC, North region, October 26, Problem H