Strawberry Feeding and Matchstick Allocation

Slavko has n rabbits numbered from \(1\) to \(n\). Every day, he buys \(S\) strawberries and selects a starting rabbit with index \(A\). He then distributes the strawberries consecutively: the first strawberry goes to rabbit \(A\), the second to rabbit \(A+1\), the third to rabbit \(A+2\), and so on. If \(A+S-1 > n\), only rabbits from \(A\) to \(n\) receive a strawberry.

Every rabbit has an initially empty matchbox. All \(n\) matchboxes are arranged in a row and divided into groups as follows. Let \(k\) be the largest integer satisfying \(k^2 \leq n\). Then the matchboxes are partitioned into \(\left\lceil \frac{n}{k} \right\rceil\) groups, where the first \(k\) matchboxes form the first group, the next \(k\) form the second, and so on (the last group may have fewer than \(k\) matchboxes). Each group has an associated cup placed next to the matchboxes of that group.

After distributing strawberries, for each rabbit that received a strawberry Slavko intends to place one matchstick into its matchbox. However, if in any group every matchbox receives a matchstick (i.e. all rabbits in the group got a strawberry), instead of placing a matchstick in each matchbox of that group, Slavko places just one matchstick into the cup corresponding to that group. For a given day, the total matchstick count used is the sum of matchsticks placed in all matchboxes and cups.

Your task is to compute, for each day, the total number of matchsticks placed according to the above rules.

Note: All formulas are provided in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of rabbits and \(m\) is the number of days. Each of the following \(m\) lines contains two integers \(S\) and \(A\) representing the number of strawberries purchased on that day and the starting rabbit index respectively.

outputFormat

For each day, output a single line containing the total number of matchsticks placed in all matchboxes and cups on that day.

sample

11 1
6 5

4