60015 수열과 쿼리 46 Diamond V

문제

길이 N의 수열 [A_1, A_2, …, A_N]과 Q개의 쿼리가 주어진다. 각 쿼리 X_i에 대해, 수열 [A_1 + X_i, A_2 + X_i, …, A_N + X_i]의 최대 연속 구간 합을 계산하시오.

최대 연속 구간 합은 모든 연속 구간 합 중 최댓값이다.

입력

첫째 줄에 N, Q가 주어진다. (1 ≤ N, Q ≤ 1,000,000)

둘째 줄에 A_1, …, A_N이 주어진다. (-10^9 ≤ A_i ≤ 10^9)

셋째 줄에 X_1, …, X_Q가 주어진다. (-10^9 ≤ X_i ≤ 10^9)

출력

Q개의 줄에 각 쿼리의 답을 출력한다.

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