Slavko 每天用各种水果和蔬菜喂养他的 $N$ 只兔子。然而，兔子们最喜欢的还是草莓。在隆冬时节，草莓很难买到且价格昂贵，因此 Slavko 只把草莓分给他的部分兔子。

Slavko 将兔子从 $1$ 到 $N$ 进行编号。为了记录每只兔子得到了多少个草莓，Slavko 决定采用以下草莓分配流程。

每天，Slavko 会购买一定数量 $S$ 的草莓，并选择某只兔子 $A$ 获得第一个草莓。兔子 $A+1$ 将获得第二个草莓，兔子 $A+2$ 获得第三个，依此类推。

每只兔子都分配有一个初始为空的火柴盒，这 $N$ 个火柴盒排成一排。

设 $K$ 为满足 $K \cdot K \le N$ 的最大整数。每 $K$ 个火柴盒（从第一个开始）旁边都会放一个杯子。我们称连续的 $K$ 个火柴盒及其旁边的杯子组成一个“块”（block）。

在给兔子们分完草莓后，Slavko 会在每只分到草莓的兔子对应的火柴盒中放入一根火柴，除非他需要在一个块内的所有火柴盒中都放入火柴。此时，他不会在块内的所有火柴盒中放入火柴，而是会在该块对应的杯子中放入一根火柴。

一只兔子收到的草莓总数可以通过其火柴盒中的火柴数加上其对应杯子中的火柴数来计算。

例如，假设有 $11$ 只兔子，即 $N=11$。数字 3 是满足其平方不超过 11 的最大整数，因此 $K=3$。这里将有四个块，其中最后一个是不完整的，仅包含两个火柴盒。如果 Slavko 购买了 6 个草莓，并将第一个草莓分给第 5 只兔子，那么杯子和火柴盒的状态将为：

编写一个程序来模拟上述过程，已知兔子的数量 $N$、天数 $M$ 以及这 $M$ 天中每天的数值 $S$ 和 $A$。

对于每一天，输出在当天 Slavko 放入火柴的所有火柴盒和杯子中，火柴的总数。

输入格式

第一行包含两个由空格隔开的整数 $N$ 和 $M$（$1 \le N, M \le 100\,000$），分别表示兔子的数量和天数。

接下来的 $M$ 行，每行包含两个由空格隔开的整数 $S$ 和 $A$。这些数字表示 Slavko 在当天购买了 $S$ 个草莓，并且兔子 $A$ 将收到第一个草莓（$1 \le A \le N$，$1 \le A+S-1 \le N$）。

输出格式

输出 $M$ 行，每行一个整数。第 $k$ 行应包含在第 $k$ 天中，Slavko 放入火柴的所有火柴盒和杯子中，火柴的总数。

样例

输入样例 1

11 3
6 5
3 1
11 1

输出样例 1

4
1
6

输入样例 2

16 3
2 2
12 3
6 11

输出样例 2

2
7
3

说明

在第一个样例中，有 11 只兔子和 11 个火柴盒，以及 4 个块，如上图所示。

• 在第一天，Slavko 将草莓分给第 5 到第 10 只兔子，将火柴放入第 5、6 和 10 号火柴盒中，并在第 3 个杯子中放入一根火柴。在此之前，他所使用的火柴盒和杯子中没有其他火柴，因此输出为 4。
• 在第二天，Slavko 将草莓分给第 1 到第 3 只兔子，仅在第 1 个杯子中放入一根火柴。
• 在第三天，Slavko 将草莓分给所有的兔子，在每个杯子中各放入一根火柴。在将 4 根火柴放入杯子后，他所使用的杯子中共有 6 根火柴，因此输出为 6。