수열과 쿼리

길이 $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]$의 최대 연속 구간 합을 계산하라.

• 주어지는 모든 수는 정수이다.
• $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]$의 최대 연속 구간 합을 출력하라.