Rad Radish Dishes

Arlene is a world renowned radish farmer who is quite busy since the radish season is underway. Radishes are a fast growing crop, and a radish plant will be ready for harvest after $M$ days. On the first $M$ days of the radish season Arlene has planted some number of radishes on each day.

On the following $N$ days of the radish season, Arlene will harvest, plant, and sell radishes. On the morning of the $i$-th day Arlene will harvest all radishes that are ready and plant $p_i$ new radishes. In the afternoon she will go to the farmer's market and wants to sell exactly $s_i$ radishes. However, despite Arlene's meticulous planning, she will sometimes have not harvested enough radishes to sell exactly $s_i$ of them. In this case she will not sell any radishes, and to figure out far off her numbers are, she wants to work out how many additional days she would have to wait to be able to sell $s_i$ radishes with the currently planted radishes.

Arlene has asked for your help to implement a program to work this out for her.

Input

The first line will contain two space separated integers $N$ and $M$.

The second line will contain $M$ space separated integers, corresponding to the number of radishes planted by Arlene on the first $M$ days.

The following $N$ lines will contain two space separated integers $p_i$ and $s_i$, corresponding to the number of radishes planted and the number of radishes Arlene wants to sell each day over the next $N$ days.

Output

Output $N$ lines each with a single integer, the minimum number of days that Arlene would have to wait, or -1 if not enough radishes are planted.

Constraints

• $1 \le N \le 100,000$
• $2 \le M \le 100,000$
• At most $1,000,000,000$ radishes are planted or sold on any given day.

Subtasks

• Subtask 1 (+22%): $N, M \le 1,000$
• Subtask 2 (+27%): There will always be either not enough radishes planted, or enough radishes to sell $s_i$ of them.
• Subtask 3 (+17%): $p_i, s_i \le 100$ for all $1 \le i \le N$
• Subtask 4 (+34%): No further constraints.

Notes

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64 bit integer type to avoid integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

Sample Explanations

Sample 1

In this case case $N = 3$ and $M = 4$. On the first four days of the season Arlene has planted $4$, $3$, $5$, and $1$ radishes respectively.

On the fifth day the four radishes planted on the first day are harvested, and one new radish is planted. Arlene then sells two of the four radishes and has two radishes left over.

On the sixth day three radishes are harvested and two radishes are planted. Arlene now has $2 + 3 = 5$ radishes but wants to sell $7$ so she cannot sell any. If Arlene were to wait one more days she would have $2 + 3 + 5 = 10$ radishes which would be enough to sell $7$.

On the seventh day five radishes are harvested and eight are planted, leaving Arlene with $5 + 5 = 10$ radishes. Arlene then sells five of these and has five left over.