Background

After thousands of bombardments and thousands of collisions, the robust No. 201 Large Graviton Accelerator remains intact. This is its thousandth experiment...

The high-frequency perturbed gravitational field in the accelerator excites $n$ gravitons. Your experimental goal is to make them coexist simultaneously for $10^{-12}$ seconds.

These $n$ gravitons are arranged uniformly in a ring within the accelerator. Each graviton possesses a certain gravitational enthalpy, representing its energy. Gravitational enthalpy is a discrete scalar. Unlike thermal enthalpy, gravitational enthalpy is defined in the integer domain, meaning it can be negative. When two gravitons are close to each other, if the product of their gravitational enthalpies is non-negative, they will attract each other and annihilate rapidly; conversely, if the product of their gravitational enthalpies is negative, the two particles will repel each other and reach a relatively stable state of coexistence. Gravitons have a long lifespan when they exist independently; that is, these $n$ gravitons can stably coexist for $10^{-12}$ seconds if and only if no two adjacent gravitons annihilate. You need to change the gravitational enthalpy of these gravitons through several interference operations in the extremely short time after the gravitons are excited and before they annihilate, so that they can coexist stably.

Description

Now, we describe this experiment quantitatively. The gravitons are arranged in a ring, and we number these gravitons clockwise from $0$ to $n-1$. That is, graviton $i$ is adjacent to graviton $(i-1) \bmod n$ and graviton $(i+1) \bmod n$. Initially, the gravitational enthalpy of graviton $i$ is $a_i$ units. You need to ensure that for all $i \in [0, n)$, $a_i \times a_{(i+1) \bmod n} < 0$. To achieve this, you can perform several operations. In each operation, you can select one graviton to interfere with. If you interfere with graviton $i$, it causes $a_{(i-1) \bmod n}$ and $a_{(i+1) \bmod n}$ to both decrease by $a_i$, and then $a_i$ becomes $-a_i$. You cannot interfere with two particles simultaneously. You need to calculate the minimum number of such interference operations required.

As expected, the next part is the unexpected situation you encounter. Your experiment has been interfered with by irresistible factors. Specifically, among the gravitons you excited, two adjacent gravitons $p$ and $(p+1) \bmod n$ unexpectedly increase their gravitational enthalpy by $v$ simultaneously. You have predicted the interference and obtained $m$ possible scenarios. Now, you need to calculate, for each scenario, the minimum number of interference operations required if the initial state changes as described above.

Of course, there is always a possibility that the experiment fails. If you find it impossible to reach the goal through interference, please report that there is no solution.

Input

The input file contains several lines, each containing several integers, with adjacent integers on the same line separated by a space.

The first line contains two integers $n, m$.

The second line contains $n$ integers, where the $i$-th number is $a_{i-1}$.

The next $m$ lines each contain two integers $p, v$, representing an interference prediction.

Output

Output $m$ lines, each containing one integer. The integer on the $i$-th line is your answer for the $i$-th prediction. If the goal can be reached under that prediction, output the minimum number of interference operations; otherwise, output $-1$ to indicate that there is no solution.

Examples

Input 1

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

Output 1

5
3

Note 1

One possible scheme for the second guess:

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

Input 2

5 2
0 0 0 0 0
1 2
0 1

Output 2

-1
-1

Input 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

Output 3

20
23
21
22
21
20
21
21
22
22

Constraints

Thousands of experiments, thousands of particles, thousands of guesses... one thousand times one hundred is your limit.

This problem uses bundled testing, divided into the following subtasks, each corresponding to different data range limits. If you pass all test cases within a subtask, you will receive the score corresponding to that subtask.

• 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$.

In addition, it is guaranteed that all test cases satisfy: $n \ge 3$, $0 \le p < n$, $|v|, \sum_{i=0}^{n-1} |a_i| \le 10^8$, and all input numbers are integers.