Slavko has ~N~ 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 ~1~ through ~N~. 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 ~S~ of strawberries and chooses some rabbit ~A~ to get the first strawberry. Rabbit ~A+1~ will get the second strawberry, rabbit ~A+2~ the third etc.

Every rabbit is assigned an initially empty matchbox, the ~N~ matchboxes forming a single row. Let ~K~ be the largest integer such that ~K \cdot K \le N~. Every group of ~K~ matchboxes (starting with the first) will also have a cup next to them. We say that ~K~ 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 ~11~ rabbits, that is ~N=11~. The number three is the largest integer which, when squared, gives a result of at most ~11~, so ~K=3~. 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 ~N~, the number of days ~M~, and the numbers ~S~ and ~A~ for each of the ~M~ 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 ~N~ and ~M~ separated by a space ~(1 \le N, M \le 100\,000)~, the number of rabbits and days.

Each of the following ~M~ lines contains two integers ~S~ and ~A~ separated by a space. These numbers mean that Slavko purchased ~S~ strawberries that day and that rabbit ~A~ will receive the first one ~(1 \le A \le N, 1 \le A+S-1 \le N)~.

Output Specification

Output ~M~ numbers, each on a separate line. The ~k^{th}~ line should contain the total number of matches in all matchboxes and cups that Slavko used on day ~k~.

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 ~11~ rabbits and matchboxes, and four blocks, as shown in the image from the description.

1. On the first day, Slavko gives strawberries to rabbits ~5~ through ~10~, putting matches into matchboxes ~5, 6~ and ~10~, 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.

2. On the second day, Slavko gives strawberries to rabbits ~1~ through ~3~, putting just one match into the first cup.

3. 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.