Description

小Tu的OJ平台密码忘记了，但是他记得密码藏在了如下图7个小人中，小人们都围成了一个圈，它们有的面朝内，有的面朝外，如下图：

有n个小人围成一圈，已知它们的职业和朝向。现在第1个小人告诉小Tu一个包含m条指令的谜题。其中第z条指令形如「左数/右数第si个玩具小人」。你需要输出依次数完这些指令后，到达的玩具小人的职业。

Input Format

输入的第一行包含西个正整数n,m,表示玩具小人的个数和指令的条数。

接下来n行,每行包含一个整数和一个字符串,以逆时针为顺序给出每个玩具小人的朝向和职业。其中0表示朝向圈内, 1表示朝向圈外。保证不会出现其他的数。字符串长度不超过10且仅由小写字母构成,字符串不为空,并且字符串两两不同。 整数和字符串之问用一个空格隔开。

接下来m行,其中第i行包含两个整数ai,si,表示第i条指令。若ai= 0,表示向左数si个人;若ai= 1 ,表示向右数si个人。保证ai不会出现其他的数, 1≤ si<n。

Output Format

输出一个字符串，表示从第一个读入的小人开始，依次数完m条指令后到达的小人的职业。

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

writer

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

y

Hint

【数据范围】

1≤n，m≤100000

【子任务】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

其中一些简写的列意义如下:

1. 全朝内:若为“√”,表示该测试点保证所有的玩具小人都朝向圈内;
2. 全左数:若为“√”,表示该测试点保证所有的指令都向左数,即对任意的1≤z≤m, ai=0;
3. si= 1:若为“√”,表示该测试点保证所有的指令都只数1个,即对任意的1≤z≤m, si=1;
4. 职业长度为1 :若为“√”,表示该测试点保证所有玩具小人的职业一定是一个长度为1的字符串。</p>

   Source

   NOIP2016-S改编题目