Beauty of L Arrays

Inventor L has created a new data structure called the L array. An L array has the ability to add (or subtract) a constant to the entire array in O(1) time. You are given an array a of length N. Define \(f(i,j)=\left|\sum_{p=i}^{j}a_p\right|\) for 1 \le i \le j \le N, where \(|x|\) denotes the absolute value of \(x\). The beauty of an array is defined as

\[ \max_{1\leq i\leq j\leq N} f(i,j), \]

Initially, you are given the array a. Then, there will be several operations. In each operation, a number x is added to every element of the array. After each such update, output the beauty of the new array.

Note: Your solution must process queries online.

inputFormat

The first line contains two integers N and Q (1 ≤ N, Q ≤ 10⁵), representing the size of the array and the number of queries.

The second line contains N integers a₁, a₂, ..., a_N (|a_i| ≤ 10⁹), the elements of the array.

Each of the next Q lines contains a single integer x (|x| ≤ 10⁹) indicating that x is added to every element of the array. The updates are cumulative.

outputFormat

For each query, output a single line containing one integer, the beauty of the current array after performing the update.

sample

5 3
1 -2 3 -4 5
2
-3
1

13
6
5