题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

本题测试数据极大，评测时可能需要 2-3 分钟时间预加载数据。

题目描述

对于一个长度为 $l$ 的序列 $[B_1, B_2, \ldots, B_l]$，序列的连续子区间被定义为像 $[B_i, B_{i+1}, \ldots, B_j]$ 这样在序列中连续出现的数的子序列。连续子区间不能为空。即，必须满足 $1 \le i \le j \le l$。

对于一个长度为 $l$ 的序列 $[B_1, B_2, \ldots, B_l]$，序列的最大连续子区间和被定义为该序列所有连续子区间的元素和中的最大值。例如，序列 $[6, -7, 3, -1, 5, 2]$ 的最大连续子区间和是 9，这可以通过选取子区间 $[3, -1, 5, 2]$ 得到。如果用数学符号表示序列 $B$ 的最大连续子区间和，则为 $\max_{1 \le i \le j \le l}(\sum_{k=i}^{j} B_k)$。

给定一个长度为 $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]$ 的最大连续子区间和。

输入格式

第一行给定 $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]$ 的最大连续子区间和。

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

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

提示

限制条件

• 所有给定的数都是整数。
• $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 分) 无额外限制条件。