수열과 쿼리 46

길이 $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$ 이다.