Lawnmower

There is a lawn in front of Martynas's house. The lawn can be viewed as a line of $N$ centimeters, with one tuft of grass growing at every centimeter. The tuft at position $i$ ($1 \le i \le N$) has height $a_i$ centimeters.

The grass has never been cut, so it is hard to even take a walk across the lawn, let alone have a picnic.

Martynas bought a lawnmower and plans to cut most of the grass over $M$ days. Day $j$ ($1 \le j \le M$) proceeds as follows, in order:

• Morning: every tuft that is not yet fully cut ($a_i \ne 0$) grows by $1\,\text{cm}$.
• Day: Martynas drives the lawnmower across the lawn $b_j$ times. Each pass reduces the height of every uncut tuft by $1\,\text{cm}$ (a height never drops below $0$).
• Evening: he counts the total height of grass still left uncut.

For example, suppose the lawn is $4\,\text{cm}$ long ($N = 4$) and the tuft heights are $1, 2, 1, 3$. Martynas works for $M = 2$ days, driving across the lawn $b_1 = 2$ times on the first day and $b_2 = 1$ time on the second day.

On the morning of day 1 every tuft grows by $1\,\text{cm}$, giving $2, 3, 2, 4$. During the day he mows twice, so each tuft loses $2\,\text{cm}$, leaving $0, 1, 0, 2$; in the evening $0 + 1 + 0 + 2 = 3\,\text{cm}$ of grass remains.

On the morning of day 2 only the tufts that still have grass grow (the first and third stay at $0$), giving $0, 2, 0, 3$. He mows once, leaving $0, 1, 0, 2$; in the evening $0 + 1 + 0 + 2 = 3\,\text{cm}$ remains again.

Given the initial state of the lawn and the mowing plan for $M$ days, compute the total height of grass left uncut in the evening of each of the $M$ days.

• The first line contains an integer $N$ — the length of the lawn.
• The second line contains $N$ space-separated integers $a_i$ ($1 \le i \le N$) — the heights of the grass tufts.
• The third line contains an integer $M$ — the number of days Martynas mows the grass.
• The fourth line contains $M$ space-separated integers $b_j$ ($1 \le j \le M$) — the number of times the lawn is mowed on day $j$.

Print $M$ lines. Line $k$ ($1 \le k \le M$) must contain a single integer — the total height of grass (in centimeters) left uncut at the end of day $k$.

• $1 \le N, M \le 100000$
• $1 \le a_i \le 1000000$ ($1 \le i \le N$)
• $1 \le b_j \le 1000000$ ($1 \le j \le M$)

Note that the computation may require a $64$-bit integer type (long long in C/C++).