60015 수열과 쿼리 Diamond V

문제

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

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

길이 $N$의 수열 $[A_1 , A_2 , \dots , A_N ]$과 $Q$개의 쿼리가 주어진다. $i$번째 쿼리는 하나의 정수 $X_i$로 표현된다. $X_i$가 주어졌을 때, 수열 $[A_1 + X_i , A_2 + X_i , \dots , A_N + X_i ]$의 최대 연속 구간 합을 계산하라.

입력

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

두 번째 줄에 $A_1 , A_2 , \dots , A_N$이 공백을 사이에 두고 주어진다.

세 번째 줄에 $X_1 , X_2 , \dots , X_Q$가 공백을 사이에 두고 주어진다.

출력

$Q$개의 줄을 출력하라. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 수열 $[A_1 + X_i , A_2 + X_i , \dots , A_N + X_i ]$의 최대 연속 구간 합을 출력하라.

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 1\, 000\, 000$
• $1 ≤ Q ≤ 1\, 000\, 000$
• $1 ≤ i ≤ N$인 모든 $i$에 대해 $−10^9 ≤ A_i ≤ 10^9$ 이다.
• $1 ≤ i ≤ Q$인 모든 $i$에 대해 $−10^9 ≤ X_i ≤ 10^9$ 이다.

서브태스크

번호	배점	제한
1	5	$N, Q ≤ 300$
2	5	$N ≤ 300$
3	28	$N ≤ 10\, 000$
4	17	$N ≤ 125\, 000$
5	16	$N ≤ 250\, 000$
6	15	$N ≤ 500\, 000$
7	14	추가 제약 조건 없음.

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