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.

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.

The first line contains the integers \(N\) and \(M\) separated by a space (\(1 \le N, M \le 100000\)), 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 \(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\).

riseoj 작성

출처 COCI 2008/2009 Contest 5