题目描述

小$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 200000$

$|a_i| \le 200000$

$0 \le x_i \le 800000$