For a sequence of length $l$, $[B_1, B_2, \ldots, B_l]$, a contiguous subarray is defined as a subsequence of numbers that appear consecutively in the sequence, written as $[B_i, B_{i+1}, \ldots, B_j]$. A contiguous subarray cannot be empty; that is, it must satisfy $1 \le i \le j \le l$.

For a sequence of length $l$, the maximum subarray sum is defined as the maximum possible sum of elements over all its contiguous subarrays. For example, for the sequence $[6, -7, 3, -1, 5, 2]$, the maximum subarray sum is $9$, which can be obtained by choosing the contiguous subarray $[3, -1, 5, 2]$.

The maximum subarray sum of a sequence $B$ is denoted mathematically as $\max(B)$.

You are given a sequence of length $N$, $[A_1, A_2, \ldots, A_N]$, and $Q$ queries. The $i$-th query is represented by an integer $X_i$. Given $X_i$, compute the maximum subarray sum of the sequence $[A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]$.

Constraints

All given numbers are integers.

• $1 \le N \le 1{,}000{,}000$
• $1 \le Q \le 1{,}000{,}000$
• For all $i$ with $1 \le i \le N$, $-10^9 \le A_i \le 10^9$
• For all $i$ with $1 \le i \le Q$, $-10^9 \le X_i \le 10^9$

Scoring

1. (5 points) $N, Q \le 300$
2. (5 points) $N \le 300$
3. (28 points) $N \le 10{,}000$
4. (17 points) $N \le 125{,}000$
5. (16 points) $N \le 250{,}000$
6. (15 points) $N \le 500{,}000$
7. (14 points) No additional constraints.

Input Format

• The first line contains two integers $N$ and $Q$ separated by a space.
• The second line contains $A_1, A_2, \ldots, A_N$ separated by spaces.
• The third line contains $X_1, X_2, \ldots, X_Q$ separated by spaces.

Output Format

Print $Q$ lines. On the $i$-th line $(1 \le i \le Q)$, output the maximum subarray sum of the sequence $[A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]$.

Example

Example 1

Input

6 15
6 -7 3 -1 5 2
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

Output

-1
0
1
2
3
4
5
9
14
20
26
32
38
44
50

Example 2

Input

10 15
-2 6 3 -8 1 2 0 -3 9 6
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

Output

2
3
5
7
9
11
13
16
25
34
44
54
64
74
84