题目描述

小雨收藏了一套造型各异的玩具小人，每个小人都有一种职业，并且任何两个小人的职业都不同。

有一天，这些玩具小人围成一圈，把小雨的钥匙藏了起来。他们有的面朝圆心，有的面朝圈外。站在圈中的小人给了小雨一条线索：“钥匙藏在从我开始向左数第 $3$ 个小人的向右数第 $1$ 个小人的向左数第 $2$ 个小人那里。”

小雨很快意识到，小人的朝向决定了左右的实际方向：面朝圈内的小人，他的左边是顺时针方向，右边是逆时针方向；而面朝圈外的小人恰好相反，左边是逆时针方向，右边是顺时针方向。

小雨一边辨认一边数：

• singer 面朝圈内，他的左数第 $3$ 个是 archer；
• archer 面朝圈外，他的右数第 $1$ 个是 thinker；
• thinker 面朝圈外，他的左数第 $2$ 个是 writer。

于是钥匙就在 writer 那里！

为了以后不再被这类谜题难住，小雨请你编写程序来解决它。谜题的形式如下：$n$ 个玩具小人围成一圈，已知每个小人的朝向与职业。现在从第 $1$ 个玩具小人出发，依次执行 $m$ 条指令，第 $z$ 条指令形如“向左数/向右数第 $s$ 个玩具小人”。请你输出依次执行完这些指令后，最终到达的玩具小人的职业。

输入格式

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

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

接下来 $m$ 行，其中第 $i$ 行包含两个整数 $a_i,s_i$，表示第 $i$ 条指令。若 $a_i=0$，表示向左数 $s_i$ 个人；若 $a_i=1$，表示向右数 $s_i$ 个人。保证 $a_i$ 不会出现其他的数，$1 \le s_i \lt n$。

输出格式

输出一个字符串，表示从第一个读入的小人开始，依次数完 $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

提示

样例 1 说明

这组数据就是【题目描述】中提到的例子。

数据范围与约定

对于 $80\%$ 的测试点，$n = 20$，$m = 1000$；

对于 $100\%$ 的测试点，$n \le 10^5$，$m \le 10^5$。

部分测试点保证以下特殊性质之一或若干：所有小人都朝向圈内；所有指令都向左数；所有指令的 $s_i$ 都等于 $1$；所有职业字符串长度都为 $1$。