Slavko has rabbits that he feeds every day with various fruits and vegetables. Rabbits, however, prefer strawberries above all else. Strawberries are hard to find and expensive in the middle of winter, so Slavko only gives strawberries to part of his rabbits.
Slavko numbered the rabbits through . To help keep track of how many strawberries each of the rabbits got, Slavko decided on the following strawberry allocation procedure.
Every day Slavko purchases some number of strawberries and chooses some rabbit to get the first strawberry. Rabbit will get the second strawberry, rabbit the third etc.
Every rabbit is assigned an initially empty matchbox, the matchboxes forming a single row. Let be the largest integer such that . Every group of matchboxes (starting with the first) will also have a cup next to them. We say that consecutive matchboxes with their cup form a block.
After giving the rabbits their strawberries, Slavko will put a single match into the matchbox of every rabbit that got a strawberry, unless he would be putting a match into all matchboxes in a block.
Instead of putting matches into all matchboxes in a block, he will put a single match in the appropriate cup.
The total number of strawberries received by a rabbit can be calculated as the number of matches in its matchbox plus the number of matches in its cup.
For example, assume that there are rabbits, that is . The number three is the largest integer which, when squared, gives a result of at most , so . There will be four blocks, the last of them incomplete with only two matchboxes. If Slavko buys 6 strawberries and gives the first of them to rabbit 5, the state in the cups and matchboxes will be:
Write a program that simulates the above procedure, knowing the number of rabbits , the number of days , and the numbers and for each of the days.
For every day, output the total number of matches in all matchboxes and cups that Slavko added matches to on that day.
Input Specification
The first line contains the integers and separated by a space , the number of rabbits and days.
Each of the following lines contains two integers and separated by a space. These numbers mean that Slavko purchased strawberries that day and that rabbit will receive the first one .
Output Specification
Output numbers, each on a separate line. The line should contain the total number of matches in all matchboxes and cups that Slavko used on day .
Sample Input 1
11 3
6 5
3 1
11 1
Sample Output 1
4
1
6
Sample Input 2
16 3
2 2
12 3
6 11
Sample Output 2
2
7
3
In the first example, there are rabbits and matchboxes, and four blocks, as shown in the image from the description.
On the first day, Slavko gives strawberries to rabbits through , putting matches into matchboxes and , and one into the third cup. Before this there were no other matches in the matchboxes and cups he used, so the output is four.
On the second day, Slavko gives strawberries to rabbits through , putting just one match into the first cup.
On the third day, Slavko gives strawberries to all his rabbits, putting one match into every cup. After putting the four matches into cups, there is a total of six matches in the cups he used, so the output is six.
Comments