Description

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 stood in a circle; some were facing inward, and some were facing outward. As shown in the figure:

At this moment, singer told Xiao Nan a riddle: “The glasses are with the toy figure reached by: counting $3$ to the left from me, then $1$ to the right, then $2$ to the left.”

Xiao Nan found that the orientation of the toy figures is crucial in this riddle, because the notions of left and right are opposite for inward- and outward-facing figures: for a toy figure facing inward, its left is the clockwise direction and its right is the counterclockwise direction; for a toy figure facing outward, its left is the counterclockwise direction and its right is the clockwise direction.

While struggling to recognize the toy figures, Xiao Nan counted:

singer is facing inward; the $3$rd to the left is archer.

archer is facing outward; the $1$st to the right is thinker.

thinker is facing outward; the $2$nd to the left is writer.

So the glasses are with writer!

Although he found his glasses, Xiao Nan was still worried. If next time there are more toy figures hiding his glasses, or the riddle is longer, he might not be able to find them. So Xiao Nan hopes you can write a program to solve similar riddles. Specifically:

There are $n$ toy figures standing in a circle, and their professions and orientations are known. Now the $1$st toy figure gives Xiao Nan a riddle consisting of $m$ instructions, where the $z$-th instruction is of the form “count $s$ toy figures to the left/right.” You need to output the profession of the toy figure you end up at after performing these instructions in order.

Input Format

The first line contains two positive integers $n,m$, the number of toy figures and the number of instructions.

The next $n$ lines each contain an integer and a string, giving each toy figure’s orientation and profession in counterclockwise order. Here $0$ indicates facing inward, and $1$ indicates facing outward. No other numbers will appear. The string length is at most $10$, consists only of English letters, is non-empty, and all strings are pairwise distinct. There is exactly one space between the integer and the string.

The next $m$ lines each contain two integers $a_i,s_i$, describing the $i$-th instruction. If $a_i=0$, count $s_i$ people to the left; if $a_i=1$, count $s_i$ people to the right. It is guaranteed that no other numbers appear for $a_i$, and $1 \le s_i < n$.

Output Format

Output a single string: starting from the first toy figure read, the profession of the toy figure reached after performing all $m$ instructions in order.

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

Sample 1 explanation

This set of testdata is exactly the example mentioned in the Description.

Subtasks

Subtasks specify characteristics of some testdata. If you have difficulty solving the full problem, you can try to solve only part of the testdata.

The scale and characteristics for each test point are shown in the table below:

Some abbreviated columns mean:

• All facing inward: If $\surd$, this test point guarantees all toy figures face inward.
• All count to the left: If $\surd$, this test point guarantees all instructions count to the left, i.e., for any $1\leq z\leq m, a_i=0$.
• $s=1$: If $\surd$, this test point guarantees all instructions count exactly $1$ person, i.e., for any $1\leq z\leq m,s_i=1$.
• Profession length is $1$: If $\surd$, this test point guarantees every toy figure’s profession is a string of length $1$.

Translated by ChatGPT 5