K. Financial Discipline
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Gennady is a big spender, and as a result he is constantly broke. Being tired of that, Gennady devised a strategy to get his finances in order.

Right now he has $$$0$$$ coins. For each of the next $$$n$$$ days, he knows how much money he will earn (during the $$$i$$$-th day, he will earn $$$a_i$$$ coins). During each day, after receiving the coins, Gennady plans to go shopping and spend $$$X$$$ coins ($$$X$$$ is the same for all days). If he has less than $$$X$$$ coins when he goes shopping, he will simply spend them all, i.e. he will have $$$0$$$ coins at the beginning of the next day. Otherwise, he will spend exactly $$$X$$$ coins.

You have to process $$$q$$$ queries. The $$$j$$$-th query consists of a single number $$$X_j$$$, and your task is to find out how much money Gennady will have after $$$n$$$ days if he uses that value as $$$X$$$ in his strategy.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) — the number of days to consider and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of coins Gennady earns during the $$$i$$$-th day.

The third line contains $$$q$$$ integers $$$X_1, X_2, \dots, X_q$$$, where $$$X_j$$$ ($$$0 \le X_j \le 10^9$$$) — the value of $$$X$$$ for the $$$j$$$-th query.

Output

Print $$$q$$$ integers. The $$$j$$$-th integer should be the answer to the $$$j$$$-th query.

Examples
Input
3 5
1 2 3
0 1 2 3 4
Output
6 3 1 0 0
Input
6 5
0 11 100 0 20 57
27 10 40 5 67
Output
69 138 17 163 0
Note

The third query from the example is processed as follows:

  1. on the first day, Gennady earns $$$1$$$ coin;
  2. Gennady plans to spend $$$2$$$ coins. But since he has only $$$1$$$ coin, he spends it and has $$$0$$$ coins left;
  3. on the second day, Gennady earns $$$2$$$ coins;
  4. he spends these $$$2$$$ coins the same day, and at the end of the day, he has $$$0$$$ coins left;
  5. on the third day, Gennady earns $$$3$$$ coins;
  6. he spends $$$2$$$ coins that day, and at the end of the day, he has $$$1$$$ coin left.