题目背景

千百次轰击，千百场碰撞，坚固的二〇一号大型引力子加速器完好如初。这是它的第千百个实验……

加速器中被高频扰动的引力场激发出 $n$ 个引力子。你们的实验目标是使得它们同时存在 $10^{-12}$ 秒。

这 $n$ 个引力子环状均匀地排列在加速器中。每个引力子拥有一定的引力焓，代表着它的能量。引力焓是一个离散的标量。不同于热力焓值，引力焓定义在整数域内，也就是说，它是可负的。当两引力子距离较近时，若它们的引力焓乘积非负，它们就会互相吸引、迅速湮灭；反之，当引力焓乘积为负，两粒子将会相斥、达到相对稳定的共存态。引力子独立存在时寿命很长，也就是说，这 $n$ 个引力子能稳定地共存 $10^{-12}$ 秒，当且仅当任意相邻的两个引力子不会湮灭。你们需要在引力子被激发后、它们湮灭前的极短时间内，通过若干次干涉改变这些引力子的引力焓，从而使得它们稳定地共存。

题目描述

现在，我们量化地描述这个实验。引力子排成环状，我们顺时针地给这些引力子编号，从 $0$ 到 $n-1$。也就是说，$i$ 号引力子会和 $(i-1)\bmod n$ 以及 $(i+1)\bmod n$ 号相邻。初始时，$i$ 号引力子的引力焓为 $a_i$ 个单位。你们需要使得对于所有的 $i\in [0,n)$，$a_i\times a_{(i+1)\bmod n} <0$。为了达到目的，你们可以进行若干次操作。每次操作时，你们可以选取一个引力子进行干涉。假如你们干涉的是 $i$ 号引力子，那么这会使得 $a_{(i-1)\bmod n}$ 与 $a_{(i+1)\bmod n}$ 同时减去 $a_i$，然后使 $a_i$ 变为 $-a_i$。你们不能同时干涉两个粒子。而你，需要计算出最少需要进行多少次这样的干涉。

不出意外地，接下来是你们遇到的意外。你们的实验在不可抗拒因素作用下被干扰了。具体来说，你们激发的引力子中会有相邻的两个 $p$ 号和 $(p+1)\bmod n$ 号，意外地同时增加 $v$ 的引力焓值。你们对干扰进行了预测，得到了 $m$ 种可能的情况。现在的你，需要对每种情况计算如果初始状态如上变化，最少需要进行多少次干涉。

当然，实验总有失败的可能性。如果你发现不可能通过干涉达到目标，也请你报告无解。

输入格式

输入文件有若干行，每行若干整数，同行相邻整数间用一个空格隔开。

第一行包含两个数 $n,m$。

第二行包含 $n$ 个数，第 $i$ 个数为 $a_{i-1}$ 。

接下来 $m$ 行，每行两个数 $p,v$，表示一次干扰预测。

输出格式

输出 $m$ 行，每行一个整数。第 $i$ 行的整数为你对第 $i$ 次预测的答复。如果该预测下可以达到目标，请你输出最少的干涉次数，否则请你输出 $-1$ 以表明无解。

输入输出样例

样例输入 #1

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

样例输出 #1

5
3

样例解释 #1

第二次猜测对应的一种方案：

    -1 +5 +3 +1
->  -1 +2 -3 -2
->  +1 +2 -1 +2
->  -1 +1 -1 +1

样例输入 #2

5 2
0 0 0 0 0
1 2
0 1

样例输出 #2

-1
-1

样例输入 #3

20 10
-25 33 -28 39 -2 33 -23 27 24 9 -38 -14 10 -24 -4 29 -9 25 17 37
12 -25
10 -24
16 1
2 47
0 -32
13 21
19 0
5 -23
3 24
1 41

样例输出 #3

20
23
21
22
21
20
21
21
22
22

数据范围

千百个实验，千百颗粒子，千百次猜测……一千个一百，就是你们的极限。

本题采用捆绑测试，分为以下若干个子任务，每个子任务对应不同的数据范围限制。若你通过一个子任务内的所有测试点，则你可以得到该子任务对应的得分。

• Subtask 1 (10 pts): $1 \le n,m \le 50$，$|v|,|a_i| \le 50$。
• Subtask 2 (20 pts): $1 \le n,m \le 400$。
• Subtask 3 (30 pts): $1 \le n,m \le 10^5$，$v=0$。
• Subtask 4 (40 pts): $1 \le n,m \le 10^5$。

此外，保证所有测试点满足：$n \ge 3$，$0 \le p < n$，$|v|,\sum_{i=0}^{n-1} |a_i| \le 10^8$，所有输入的数均为整数。