Financial Discipline
Description
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.
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.
Print $q$ integers. The $j$-th integer should be the answer to the $j$-th query.
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.
3 5
1 2 3
0 1 2 3 4
6 5
0 11 100 0 20 57
27 10 40 5 67
6 3 1 0 0
69 138 17 163 0
Note
The third query from the example is processed as follows:
- on the first day, Gennady earns $1$ coin;
- Gennady plans to spend $2$ coins. But since he has only $1$ coin, he spends it and has $0$ coins left;
- on the second day, Gennady earns $2$ coins;
- he spends these $2$ coins the same day, and at the end of the day, he has $0$ coins left;
- on the third day, Gennady earns $3$ coins;
- he spends $2$ coins that day, and at the end of the day, he has $1$ coin left.