수열과 쿼리 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$ 이다.