Problem Background

NOIP2016 Senior Group D1T1

Problem Description

Xiao Nan has a set of adorable toy figurines, each with a different profession.

One day, these toy figurines hid Xiao Nan's glasses. Xiao Nan found that the figurines were arranged in a circle, some facing inward and others facing outward. As shown in the following image:

Then, the singer told Xiao Nan a puzzle: "The glasses are hidden in the toy figurine to my left, the third one, and then to the right of that one, the first one, and then to the left of that one, the second one."

Xiao Nan realized that the orientation of the figurines was crucial because the left and right directions were reversed for figurines facing inward and outward: for figurines facing inward, their left is in the clockwise direction, and their right is in the counterclockwise direction; for figurines facing outward, their left is in the counterclockwise direction, and their right is in the clockwise direction.

Xiao Nan struggled to identify the figurines while counting:

The singer faces inward, the third one to the left is the archer.

The archer faces outward, the first one to the right is the thinker.

The thinker faces outward, the second one to the left is the writer.

So the glasses are hidden with the writer!

Although Xiao Nan successfully found his glasses, he was not at ease. If there were more toy figurines next time or the puzzle was longer, he might not be able to find the glasses. Therefore, Xiao Nan hopes you can write a program to help him solve similar puzzles. Such puzzles can be described as follows:

There are $n$ toy figurines arranged in a circle, with known professions and orientations. Now, the first toy figurine tells Xiao Nan a puzzle containing $m$ instructions, where the $z$-th instruction is like "count $s$ figurines to the left/right." You need to output the profession of the figurine reached after counting through these instructions.

Input Format

The first line of input contains two positive integers $n, m$, representing the number of toy figurines and the number of instructions, respectively.

The next $n$ lines, each containing an integer and a string, describe the orientation and profession of each toy figurine in counterclockwise order. Here, $0$ indicates facing inward, and $1$ indicates facing outward. The string, with a length not exceeding $10$ and consisting only of English letters, is non-empty and unique. An integer and a string are separated by a space.

The next $m$ lines, where the $i$-th line contains two integers $a_i, s_i$, describe the $i$-th instruction. If $a_i=0$, it means counting $s_i$ figurines to the left; if $a_i=1$, it means counting $s_i$ figurines to the right. It is guaranteed that $a_i$ will not have other values, and $1 \le s_i < n$.

Output Format

Output a string representing the profession of the figurine reached after counting through the $m$ instructions starting from the first input figurine.

Sample Input and Output

Input Sample #1

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

Output Sample #1

writer

Input Sample #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

Output Sample #2

y

Notes/Hints

Sample 1 Explanation

This set of data is the example mentioned in the problem description.

Subtasks

Subtasks will provide characteristics of some test data. If you encounter difficulties in solving the problem, you can try to solve only part of the test data.

The scale and characteristics of the data for each test point are as follows:

Some abbreviated column meanings are as follows:

• All inward: If marked with $\surd$, it means that all toy figurines in this test point are guaranteed to face inward.
• All left: If marked with $\surd$, it means that all instructions in this test point are guaranteed to count to the left, i.e., for any $1 \leq z \leq m, a_i=0$.
• $s=1$: If marked with $\surd$, it means that all instructions in this test point are guaranteed to count only one figurine, i.e., for any $1 \leq z \leq m, s_i=1$.
• Profession length of $1$: If marked with $\surd$, it means that all toy figurines in this test point are guaranteed to have a profession that is a string of length $1$.

见题面 Input 部分

见题面 Output 部分