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

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

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

输入格式

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

输出格式

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

输入样例

4 3
1 3
2 1
1 3

输出样例

4
3
2

数据范围

1<n<1e18 ， 1<t<100000

样例解释

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