Background

Problem Description

Xiao $L$ invented a new data structure and named it the $L$ array. An $L$ array can add or subtract a number to the entire array in $O(1)$ time. Now you are given an array $a$ of length $N$. He wants to use the $L$ array to challenge your computing ability.

Define $f(i,j)=|\sum_{p=i}^{j} a_p|$, where $|x|$ denotes the absolute value of $x$.

Define the beauty of an array as $\max_{1 \le i \le j \le N} f(i,j)$. Each time he adds $x$ to the entire array, you need to answer the beauty at that moment.

Note that your algorithm must be online.

Input Format

The first line contains two integers $N,M$, representing the array length and the number of queries.

The second line contains $N$ integers, representing the initial array $a$.

The next $M$ lines each contain one integer $x_i$. Let the previous answer be $pre$. Then for the $i$-th query, it means adding $[(x_i+pre)\%(4n+1)-2n]$ to the entire array based on the initial array. Here $\%$ denotes the modulo operation. For the first answer, $pre=0$.

Output Format

Output $M$ lines. The $i$-th line is the beauty of the array after adding $x_i$ to the entire array based on the initial array.

4 4
4 5 6 7
1
15
0
12

6
6
14
26

Hint

The four added numbers are $-7$, $-4$, $-2$, and $1$.

Constraints:

$1 \le N,M \le 200000$.

$|a_i| \le 200000$.

$0 \le x_i \le 800000$.

Translated by ChatGPT 5