题目描述

Dexter 新开了一间实验室，想对小鼠进行一系列实验。在实验室中有 $N$ 只小鼠，它们围成一个圆圈，并按顺序编号为 $0$ 到 $N-1$。

Dexter 依次进行 $M$ 次实验。对于每一次实验，参与第 $i$ 次实验的小鼠总是圆上的一个连续区间，用一对数 $(S_i,F_i)$ 表示：

• 如果 $S_i\le F_i$，则编号为

$$S_i,S_i+1,\ldots,F_i$$

的小鼠参与第 $i$ 次实验；

• 如果 $S_i>F_i$，则编号为

$$S_i,S_i+1,\ldots,N-2,N-1,0,\ldots,F_i$$

的小鼠参与第 $i$ 次实验。

任务

在每一步，Dexter 都想知道有多少只小鼠参加了到目前为止的所有实验。

换句话说，在完成第 $i$ 次实验后，需要求出同时参加了实验 $1,2,\ldots,i$ 的小鼠数量。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $A_i,B_i$。它们按如下方式确定真正的区间端点 $S_i,F_i$：

• 如果 $i=1$，则

$$S_i=A_i,\qquad F_i=B_i.$$

• 如果 $i>1$，记 $R_{i-1}$ 为第 $i-1$ 次实验后的答案，则

$$S_i=(R_{i-1}+A_i)\bmod N,$$ $$F_i=(R_{i-1}+B_i)\bmod N.$$

输出格式

应包含 $M$ 行。

第 $i$ 行输出一个整数，表示参加了实验 $1,2,\ldots,i$ 的小鼠数量。

数据范围与限制

• $1\le N\le 1\,000\,000\,000$；
• $1\le M\le 100\,000$；
• $0\le A_i,B_i<N$。

子任务

子任务	分值	限制
1	18	对所有 $1\le i\le M$，都有 $A_i\le B_i$
2	20	$1\le N,M\le 1000$
3	22	$1\le N\le 100000,\ 1\le M\le 1000$
4	20	$1\le N,M\le 100000$
5		无额外限制

样例

样例 1

输入

5 3
1 4
3 0
2 0

输出

4
3
2

解释

对于第一次实验，$S_1=1,F_1=4$，参与的小鼠为 $1,2,3,4$，所以 $R_1=4$。

对于第二次实验，

$$S_2=(3+4)\bmod 5=2,$$ $$F_2=(0+4)\bmod 5=4.$$

同时参加前两次实验的小鼠为 $2,3,4$，所以 $R_2=3$。

对于第三次实验，

$$S_3=(2+3)\bmod 5=0,$$ $$F_3=(0+3)\bmod 5=3.$$

同时参加前三次实验的小鼠为 $2,3$，所以 $R_3=2$。

样例 2

输入

6 2
4 1
2 5

输出

4
2

解释

对于第一次实验，$S_1=4,F_1=1$，参与的小鼠为 $0,1,4,5$，所以 $R_1=4$。

对于第二次实验，

$$S_2=(2+4)\bmod 6=0,$$ $$F_2=(5+4)\bmod 6=3.$$

同时参加前两次实验的小鼠为 $0,1$，所以 $R_2=2$。