Description

Slavko keeps $n$ rabbits, and every day he feeds them various fruits and vegetables. However, the rabbits like strawberries the most. Strawberries are hard to find in the middle of winter and are expensive, so Slavko only gives strawberries to some of the rabbits. Slavko numbers the rabbits from $1$ to $n$. To help track how many strawberries each rabbit gets, he decided to use the following strawberry distribution procedure.

Every day, Slavko buys $S$ strawberries, then chooses a rabbit $A$, and gives it the first strawberry. After that, rabbit $A+1$ gets the second strawberry, rabbit $A+2$ gets the third, and so on.

He assigns each rabbit a matchbox that is initially empty, and then places these $n$ matchboxes in a row. Let $k$ be the largest integer such that $k^2 \leqslant n$. Then the rabbits can be divided into $\left\lceil\dfrac{n}{k}\right\rceil$ groups, each consisting of $k$ matchboxes (starting from the first; the last group may have fewer than $k$ matchboxes). Next to each group of matchboxes, there is also a cup. We say that $k$ consecutive matchboxes and their cup form a group.

After giving the rabbits strawberries, Slavko puts one match into the matchbox of each rabbit that received a strawberry, unless he would end up putting matches into all matchboxes of some group. In that case, he does not put matches into all matchboxes of that group; instead, he puts one match into the cup of that group. In this way, the total number of strawberries received by the rabbits can be computed from the number of matches in the matchboxes plus the number of matches in the cups. For example, suppose Slavko has $11$ rabbits, i.e. $n=11$. The number $3$ is the largest integer $k$ such that $k^2 \leqslant n$, so $k=3$. Therefore, the rabbits will be divided into four groups (the last group has only two rabbits and two matchboxes), and naturally there will be four cups, as shown in the figure below:

If Slavko buys $6$ strawberries and gives the first one to rabbit $5$, then the cups and matchboxes will look as follows:

Now, write a program that is given the number of rabbits $n$, the number of days $m$, and for each of the $m$ days the number of strawberries bought $S$ and the index $A$ of the rabbit that receives the first strawberry. For each day, output the total number of matches in all matchboxes and cups that Slavko used on that day.

Input Format

The input consists of $m+1$ lines.

The first line contains two integers $n, m$, representing the total number of rabbits (also the number of matchboxes) and the number of days.
The next $m$ lines each contain two integers $S, A$. In the $i$-th of these lines, $S$ is the number of strawberries bought on day $i$, and $A$ is the index of the rabbit that receives the first strawberry.

Output Format

Output $m$ lines. The $i$-th line should contain one integer, the total number of matches in all matchboxes and cups that Slavko used on day $i$.

11 3
6 5
3 1
11 1

4
1
6

16 3
2 2
12 3
6 11

2
7
3

Hint

[Sample 1 Explanation]

For sample $1$, the arrangement of rabbits, matchboxes, and cups is exactly the example shown in the statement.

The first day is the example from the statement, so Slavko puts in $4$ matches on day $1$.

On the second day, Slavko buys $3$ strawberries and gives the first strawberry to rabbit $1$. Then rabbits $1$, $2$, and $3$ all receive strawberries. Since these three rabbits are in the same group, Slavko only needs to put one match into the first cup. Therefore, Slavko puts in $1$ match on day $2$.

On the third day, Slavko can give strawberries to all of his rabbits, so he needs to put one match into every cup. In total, he puts $4$ matches into the cups. After placing them, there are $6$ matches in the cups he used that day (that is, all cups), so the output is $6$.

[Constraints]

For all data, $1 \leqslant n, m \leqslant 10^5$, $1 \leqslant A \leqslant n$, $1 \leqslant A+S-1 \leqslant n$.

[Source]

This problem is from COCI 2008-2009 CONTEST 5 T3 JAGODA. According to the original testdata configuration, the full score is $70$ points.

Translated and整理 (zhenglǐ) by Eason_AC.

Translated by ChatGPT 5