A. Avatar queries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Avatar aang is in trouble. He's facing a threat bigger than anything he has faced before and he needs the help of former avatars. However talking with his pasts lives, is exhausting so he wants your help to find the correct avatars to contact.

You are given an array $$$a_1,a_2,\ldots,a_n$$$ where $$$a_i$$$ is how helpful the $$$i$$$-th avatar is, and $$$a_n$$$ avatar is the latest avatar before Aang. Consider that an avatar could be unhelpful rather than helpful, so he'll have a negative value.

You'll have to answer $$$q$$$ queries, consisting of a number $$$x$$$ indicating, Aang doesn't want to go further back than the $$$x$$$-th avatar. So starting from avatar $$$x+1$$$, find the maximum possible sum of helpfuness a contiguous subarray of avatars can give. Tradition indicates that Aang must recieve help from at least 1 avatar.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2\cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Each of the next $$$q$$$ lines contains one integer $$$x$$$ ($$$0 \le x \lt n$$$).

Output

For each query, print the maximum help Aang can get, even if it is negative.

Example
Input
5 4
-2 3 -1 4 -5
0
1
3
4
Output
6
6
4
-5
Note

For $$$x=0$$$, all avatars are available. For $$$x=n-1$$$, the only available avatar is $$$a_n$$$.