【2016】玩具谜题

题目描述

小南有一套玩具小人围成一圈，每个小人有朝向和职业：

• 朝向0表示面朝圈内，其左边为顺时针方向，右边为逆时针方向；
• 朝向1表示面朝圈外，其左边为逆时针方向，右边为顺时针方向。

已知n个小人按逆时针顺序给出朝向和职业，从第一个读入的小人开始，执行m条指令，每条指令形如a_i s_i：

• a_i=0表示从当前小人向左数s_i个；
• a_i=1表示从当前小人向右数s_i个。

要求输出执行完所有指令后最终到达的小人的职业。

输入描述

1. 第一行两个正整数n, m，分别表示小人个数和指令条数。
2. 接下来n行，每行一个整数（0或1）和一个字符串，按逆时针顺序给出每个小人的朝向和职业，职业字符串唯一且仅由小写字母构成，长度不超过10。
3. 接下来m行，每行两个整数a_i, s_i，表示第i条指令，保证1 ≤ s_i < n。

输出描述

输出一个字符串，为最终到达的小人的职业。

输入样例1

7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2

输出样例1

writer

样例1解释

初始位于索引0的singer（朝向0）：

1. 第一条指令a=0左数3个：朝向0左为顺时针，偏移-3，索引变为(0 - 3 + 7) %7 =4，到达朝向1的archer；
2. 第二条指令a=1右数1个：朝向1右为顺时针，偏移-1，索引变为(4 -1 +7)%7=3，到达朝向1的thinker；
3. 第三条指令a=0左数2个：朝向1左为逆时针，偏移+2，索引变为(3+2)%7=5，到达writer，输出结果。

输入样例2

10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

输出样例2

y

子任务说明

测试点分为20组，数据规模分为两档：

• 前16组：n=20, m=1e3
• 后4组：n=1e5, m=1e5 部分测试点有特殊限制（如全朝内、全左数等），可用于分步解题。