수열과 쿼리 46

문제

길이 $ll$의 수열 $[B_1,B_2,\dots ,B_l][B\_1\; ,\; B\_2\; ,\; \backslash dots\; ,\; B\_l\; ]$에 대해, 수열의 연속 구간은 $[B_i,B_{i+1},\dots ,B_j][B\_i\; ,\; B\_\{i+1\}\; ,\backslash dots\; ,\; B\_j\; ]$와 같이 수열 위에서 연속적으로 등장하는 수들의 부분 수열로 정의된다. 연속 구간은 비어 있을 수 없다. 즉, 1 ≤ i ≤ j ≤ l을 만족해야 한다.

길이 $ll$의 수열 $[B_1,B_2,\dots ,B_l][B\_1\; ,\; B\_2\; ,\; \backslash dots\; ,\; B\_l\; ]$에 대해, 수열의 최대 연속 구간 합은 수열의 모든 연속 구간의 원소의 합의 최댓값으로 정의된다. 예를 들어, 수열 [6, −7, 3, −1, 5, 2]의 최대 연속 구간 합은 $99$이며, 이는 연속 구간 [3, −1, 5, 2]를 골라서 얻을 수 있다. 수열 $BB$의 최대 연속 구간 합을 수학 기호로 표현하면 ${\max }_{1\le i\le j\le l}\left({\sum }_{k=i}^j{B}_k\right)\backslash max\_\{1\; \backslash le\; i\; \backslash le\; j\; \backslash le\; l\}\{\backslash left(\; \backslash sum\_\{k=i\}^j\{B\_k\}\; \backslash right)\}$이다.

길이 $NN$의 수열 $[A_1,A_2,\dots ,A_N][A\_1\; ,\; A\_2\; ,\; \backslash dots\; ,\; A\_N\; ]$과 $QQ$개의 쿼리가 주어진다. $ii$번째 쿼리는 하나의 정수 $X_{i}X\_i$로 표현된다. $X_{i}X\_i$가 주어졌을 때, 수열 $[A_1+X_i,A_2+X_i,\dots ,A_N+X_i][A\_1\; +\; X\_i\; ,\; A\_2\; +\; X\_i\; ,\; \backslash dots\; ,\; A\_N\; +\; X\_i\; ]$의 최대 연속 구간 합을 계산하라.

입력

첫 번째 줄에 $NN$, $QQ$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $A_1,A_2,\dots ,A_{N}A\_1\; ,\; A\_2\; ,\; \backslash dots\; ,\; A\_N$이 공백을 사이에 두고 주어진다.

세 번째 줄에 $X_1,X_2,\dots ,X_{Q}X\_1\; ,\; X\_2\; ,\; \backslash dots\; ,\; X\_Q$가 공백을 사이에 두고 주어진다.

출력

$QQ$개의 줄을 출력하라. 이 중 $ii$ (1 ≤ i ≤ Q)번째 줄에는 수열 $[A_1+X_i,A_2+X_i,\dots ,A_N+X_i][A\_1\; +\; X\_i\; ,\; A\_2\; +\; X\_i\; ,\; \backslash dots\; ,\; 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