Added Sequence

题目描述

小$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$时的美丽度。

输入输出样例

输入样例 #1

4 4
4 5 6 7
1
15
0
12

输出样例 #1

6
6
14
26

说明

四次加上的数字分别为-7,-4,-2,1。 $1 \le N,M \le 200000$ $|a_i| \le 200000$ $0 \le x_i \le 800000$