Xiao Nan has a set of cute toy figures, each with a different profession.
One day, these toy figures hid Xiao Nan's glasses. Xiao Nan found that the toy figures had formed a circle, with some facing inward and some facing outward. As shown below:
At this moment, the singer tells Xiao Nan a riddle: "The glasses are hidden at the position of the $2^{nd}$ toy figure to the left of the $1^{st}$ toy figure to the right of the $3^{rd}$ toy figure to my left."
Xiao Nan discovered that the orientation of the toy figures is crucial, because the left and right directions for figures facing inward and outward are opposite: for a toy figure facing inward, its left is clockwise and its right is counter-clockwise; for a toy figure facing outward, its left is counter-clockwise and its right is clockwise.
Xiao Nan identified the toy figures with difficulty and counted: "The $3^{rd}$ to the left of the singer is the archer." "The $1^{st}$ to the right of the archer is the thinker." "The $2^{nd}$ to the left of the thinker is the writer." "So the glasses are hidden at the writer!"
Although he successfully retrieved his glasses, Xiao Nan is still worried. If there were more toy figures or the riddle were longer next time, he might not be able to find his glasses. So Xiao Nan hopes you can write a program to help him solve similar riddles. Such a riddle can be specifically described as:
There are $n$ toy figures in a circle, and their professions and orientations are known. Now, the $1^{st}$ toy figure tells Xiao Nan a riddle containing $m$ instructions, where the $i$-th instruction is of the form "move $s_i$ toy figures to the left/right". You need to output the profession of the toy figure reached after executing these instructions in sequence.
Input
The input is read from toy.in.
The first line contains two positive integers $n$ and $m$, representing the number of toy figures and the number of instructions.
The next $n$ lines each contain an integer and a string, giving the orientation and profession of each toy figure in counter-clockwise order. $0$ represents facing inward, and $1$ represents facing outward. It is guaranteed that no other numbers appear. The length of the string does not exceed $10$, and it consists only of lowercase letters. The strings are non-empty and distinct. Integers and strings are separated by a space.
The next $m$ lines each contain two integers $a_i, s_i$, representing the $i$-th instruction. If $a_i = 0$, it means move $s_i$ figures to the left; if $a_i = 1$, it means move $s_i$ figures to the right. It is guaranteed that no other numbers appear, $1 \le s_i < n$.
Output
Output to toy.out.
Output a string representing the profession of the toy figure reached after executing the $m$ instructions, starting from the first toy figure read.
Examples
Input 1
7 3 0 singer 0 reader 0 mengbier 1 thinker 1 archer 0 writer 1 mogician 0 3 1 1 0 2
Output 1
writer
Note 1
This data set is the example mentioned in the problem statement.
Input 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 2
y
Subtasks
The subtasks provide characteristics of some test data. If you encounter difficulties in solving the problem, you can try to solve only a portion of the test data.
The data scale and characteristics for each test case are as follows:
| Test Case | $n$ | $m$ | All Inward | All Left | $s_i = 1$ | Profession Length 1 |
|---|---|---|---|---|---|---|
| 1 | $= 20$ | $= 10^3$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | |
| 2 | $\times$ | |||||
| 3 | $\checkmark$ | $\times$ | ||||
| 4 | $\times$ | |||||
| 5 | $\checkmark$ | $\checkmark$ | ||||
| 6 | $\times$ | $\times$ | ||||
| 7 | $\checkmark$ | $\times$ | ||||
| 8 | $\times$ | |||||
| 9 | $\checkmark$ | $\checkmark$ | ||||
| 10 | $\times$ | |||||
| 11 | $\checkmark$ | $\times$ | ||||
| 12 | $\times$ | |||||
| 13 | $\checkmark$ | $\checkmark$ | ||||
| 14 | $\times$ | |||||
| 15 | $\checkmark$ | $\times$ | ||||
| 16 | $\times$ | |||||
| 17 | $= 10^5$ | $= 10^5$ | $\checkmark$ | $\checkmark$ | ||
| 18 | $\times$ | |||||
| 19 | $\checkmark$ | $\times$ | ||||
| 20 | $\times$ |
The meanings of the abbreviations in the table are as follows: All Inward: If marked with "$\checkmark$", it means the test case guarantees all toy figures are facing inward; All Left: If marked with "$\checkmark$", it means the test case guarantees all instructions are to the left, i.e., for any $1 \le i \le m$, $a_i = 0$; $s_i = 1$: If marked with "$\checkmark$", it means the test case guarantees all instructions move by 1, i.e., for any $1 \le i \le m$, $s_i = 1$; Profession Length 1: If marked with "$\checkmark$", it means the test case guarantees all toy figures' professions are strings of length 1.