D. Beautiful decrease
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Meshmesh started learning about operations on sub-arrays, so his mentor gave him a problem to solve using what he has learned.

Given an array $$$A$$$ with size $$$n$$$ and $$$Q$$$ queries. In each query, Meshmesh will perform at most $$$k$$$ beautiful decreases.

In one beautiful decrease, You can decrease each element in one sub-array by 1 such that the sum of the array is minimized, and each element in the chosen sub-array must be greater than 0.

But his mentor asks him to update the array after doing the beautiful at the $$$i_{th}$$$ query and print the sum of the new array.

Note: the decreases are permanent, they change the array.

For example: given $$$n=8$$$, $$$A={3,5,4,3,3,4,1,5}$$$, $$$Q=1$$$; and first $$$k=2$$$, so the minimum sum will equal to $$$14$$$ and $$$A$$$ will be $$${1,3,2,1,1,2,0,4}$$$.

Meshmesh thinks that the problem is too difficult form him to solve and asks for your help. Can you help him ?

Input

The first line contains two integers $$$n$$$ and $$$Q$$$ $$$(1\leq n, Q \leq 10^{5})-$$$ array size and the number of questions that Meshmesh will answer.

The next line contains $$$n$$$ integers $$$A_{1}, A_{2},...A_{n}$$$ $$$(1\leq A_{i} \leq 10^{9})- $$$the given array elements.

Each of the next $$$Q$$$ lines contains $$$k_{i}$$$ $$$(1\leq k_{i} \leq 10^{5})- $$$ the number of beautiful decreases Meshmesh can perform in the array.

Output

$$$Q$$$ lines, each line contains the summation of the array after beautiful decreases.

Example
Input
8 5
3 5 4 3 3 2 1 5
2
1
2
1
1
Output
12
7
4
3
2