对于长度为 $l$ 的序列 $[B_1, B_2, \ldots, B_l]$，连续子数组 定义为在序列中位置连续出现的一段子序列，记作 $[B_i, B_{i+1}, \ldots, B_j]$。连续子数组不能为空，即必须满足 $1 \le i \le j \le l$。

对于长度为 $l$ 的序列，其 最大子数组和 定义为所有连续子数组的元素和的最大值。 例如，对于序列 $[6, -7, 3, -1, 5, 2]$，最大子数组和为 $9$，可以通过选择连续子数组 $[3, -1, 5, 2]$ 得到。

序列 $B$ 的最大子数组和用 $\max(B)$ 表示。

给定一个长度为 $N$ 的序列 $[A_1, A_2, \ldots, A_N]$，以及 $Q$ 个询问。 第 $i$ 个询问由整数 $X_i$ 表示。 对于给定的 $X_i$，请计算序列 $[A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]$ 的最大子数组和。

限制

所有给定的数均为整数。

• $1 \le N \le 1{,}000{,}000$
• $1 \le Q \le 1{,}000{,}000$
• 对所有满足 $1 \le i \le N$ 的 $i$，$-10^9 \le A_i \le 10^9$
• 对所有满足 $1 \le i \le Q$ 的 $i$，$-10^9 \le X_i \le 10^9$

子任务

1.（5 分）$N, Q \le 300$ 2.（5 分）$N \le 300$ 3.（28 分）$N \le 10{,}000$ 4.（17 分）$N \le 125{,}000$ 5.（16 分）$N \le 250{,}000$ 6.（15 分）$N \le 500{,}000$ 7.（14 分）无额外限制。

输入格式

• 第一行包含两个用空格分隔的整数 $N$ 和 $Q$。
• 第二行包含用空格分隔的 $A_1, A_2, \ldots, A_N$。
• 第三行包含用空格分隔的 $X_1, X_2, \ldots, X_Q$。

输出格式

输出 $Q$ 行。 第 $i$ 行（$1 \le i \le Q$）输出序列 $[A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]$ 的最大子数组和。

样例数据

样例 1

输入

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

输出

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

样例 2

输入

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

输出

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