横版场域论¶

预估时间限制：0.5 秒。内存限制：256 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

有 \(N\) 位同学站在一个左右循环的横版场域中，从我们的视角看，他们排成一列，从左到右编号为 \(1,\ldots,N\)。每个人要么面对我们，要么背对我们，并按照自己的朝向理解“左”和“右”。

同学们正在玩传递物品的游戏，物品最初在一号同学手中。每次，持有者会把物品传给自己左边或右边数第 \(p\) 位同学；第零位就是自己。因为场域左右循环，\(p\) 可以超过 \(N\)，跨过两端相接的位置也不会改变任何人的朝向。

每位同学都有且只有一个专业，用大写字母 A 到 Z 表示，不同同学的专业可以相同。游戏一共进行 \(M\) 次传递，请在每次传递后输出物品持有者的专业。

从观察者的视角看，\(N\) 位同学从左到右编号为 \(1,\ldots,N\) ，右端与左端相接。第 \(i\) 位同学的朝向为 \(f_i\) ：零表示背对观察者，一表示面对观察者。每个人的专业用大写字母 \(C_i\) 表示，不同同学的专业可以相同。

物品初始在一号同学处。每次给出 \(d,p\) ：零表示当前持有者自己的左方，一表示自己的右方；沿该方向数 \(p\) 个位置，交给那里的同学。数零个位置仍是本人，可以绕队列多圈。每个人的朝向始终不变。每次传递后输出新持有者的专业。

样例一的朝向和按顺序发生的五次传递

图中上箭头表示背对位于下方的观察者，下箭头表示面对观察者。下面的编号链表示每次传递后的持有者。

第一行两个整数 \(N,M\) .接下来 \(N\) 行，第 \(i\) 行给出整数 \(f_i\) 和大写字母 \(C_i\) .接下来 \(M\) 行，每行两个整数 \(d,p\) ，描述一次传递。

输出 \(M\) 行，每行一个大写字母，表示对应传递后的持有者的专业。

A
B
A
E
C

1 3
1 Z
0 0
1 1000000000
0 1

Z
Z
Z

样例 1 的持有者依次为一号、二号、一号、五号、三号。同学的左右由当时持有者的朝向决定。样例 2 只有一位同学，任意传递后仍由他持有。

对 100% 的数据：\(1\le N,M\le30000\) ，\(f_i,d\in\{0,1\}\) ，\(0\le p\le10^9\) ，\(C_i\) 为大写英文字母。

“不跨越首尾”指每次按观察者方向移动指定步数时，中途编号始终在一到 \(N\) 之间。分组中的步数之和是同一输入文件的所有 \(p\) 之和。