n个点围成一圈，顺时针编号1到n。机器人开始时位于1号点，后面我们开始向机器人发送命令，命令有2种：

1 s （顺时针走 s 步，每步一个点）

2 u （逆时针走 u 步，每步一个点）

我们共发送t个指令给机器人，输出机器人执行完每次指令后所在点的位置。

输入

第1行：2个数n，t中间用空格分隔，n为点的数量，t为指令的数量（1 < n < 1000000，1 < t < 100000）

第2~t+1行：每行2个数

输出

输出共t行，对应执行指令后，机器人所在的位置。

数据范围

1 < n < 1000000，1 < t < 100000

输入样例

4 3

1 3

2 1

1 3

输出样例

4

3

2

样例解释

1-4共4个点，顺时针围成一个圈。初始时，机器人在1号位置，顺时针走3步后到达位置4，逆时针走一步到达位置3，顺时针走3步到达位置2。