题目描述

小 $L$ 发明了一种新的数据结构，并将其命名为 $L$ 数组。$L$ 数组的作用是可以在 $O(1)$ 时间内将整个数组加上或减去一个数。现在给你一个长度为 $N$ 的数组 $a$，他想用 $L$ 数组来挑战你的计算能力。

定义 $f(i,j)=|\sum_{p=i}^{j} a_p|$ 其中 $|x|$ 表示 $x$ 的绝对值。

定义一个数组的美丽度为 $\max_{1 \le i \le j \le N} f(i,j)$，每当他将整个数组加上 $x$，请你回答此时的美丽度。

注意，你的算法必须为在线的。

输入格式

第一行输入两个整数 $N,M$，分别表示数组长度和询问数量。

第二行输入 $N$ 个整数，表示起始的数组 $a$。

接下来 $M$ 行，每行一个整数 $x_i$，设前面一次回答的答案为 $pre$，那么表示第 $i$ 次询问时在起始数组的基础上整个数组加上 $[(x_i+pre)\%(4n+1)-2n]$。其中 $\%$ 表示求余运算，第一次回答时 $pre=0$。

输出格式

输出 $M$ 行，第 $i$ 行为在起始数组的基础上整个数组加上 $x_i$ 时的美丽度。

4 4
4 5 6 7
1
15
0
12

6
6
14
26

提示

四次加上的数字分别为 -7，-4，-2，1。

$1 \le N,M \le 2\times 10^5$

$|a_i| \le 2\times 10^5$

$0 \le x_i \le 8\times 10^5$