循环路线查询

难度：T1（基础巩固）

【知识点：倍增与二进制跳跃】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

编号为 $1$ 到 $n$ 的站点连成一个环：从 $i$ 走一步到 $i+1$，从 $n$ 走一步回到 $1$。求每次询问跳转结束时的站点。

输入格式

编号$1$到$n$的站点构成固定环，$i$走一步到$i+1$，$n$到$1$。第一行$n$、$q$，随后$q$行$s$、$k$。

输出格式

每行输出走$k$步后的编号。

数据范围

$1\le n,q\le 100000$，$1\le s\le n$，$0\le k\le 10^9$。

样例输入

1 6
1 0
1 1
1 2
1 3
1 4
1 5

样例输出

1
1
1
1
1
1

样例输入 2

5 3
4 0
4 3
1 10

样例输出 2

4
2
1

样例说明 2

从 $4$ 走三步依次到 $5,1,2$；从 $1$ 走十步，绕两圈回到 $1$。