Description

Little Tu forgot the password to his OJ platform, but he remembers that the password is hidden among the seven little figures shown in the image below. The figures are arranged in a circle, some facing inward and some outward, as illustrated:

There are n little figures arranged in a circle, each with a known profession and facing direction. The first figure gives Little Tu a riddle containing m instructions. The z-th instruction is of the form "count si figures to the left/right." You need to output the profession of the figure reached after executing all these instructions in sequence.

Input Format

The first line of input contains two positive integers n and m, representing the number of little figures and the number of instructions, respectively.

The next n lines each contain an integer and a string, describing each little figure's facing direction and profession in counterclockwise order. Here, 0 indicates facing inward, and 1 indicates facing outward. No other numbers will appear. The string has a maximum length of 10, consists of lowercase letters only, is non-empty, and all strings are distinct. The integer and string are separated by a single space.

The following m lines each contain two integers ai and si, representing the i-th instruction. If ai = 0, it means count si figures to the left; if ai = 1, it means count si figures to the right. It is guaranteed that ai will not take any other values, and 1 ≤ si < n.

Output Format

Output a string representing the profession of the little figure reached after executing all m instructions in sequence, starting from the first input figure.

```input1 7 3 0 singer 0 reader 0 mengbier 1 thinker 1 archer 0 writer 1 mogician 0 3 1 1 0 2 ``` ```output1 writer ``` ```input2 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 ``` ```output2 y ``` ## Hint

【Data Range】

1 ≤ n, m ≤ 100000

【Subtask】

Subtasks describe characteristics of partial test data. If you encounter difficulties in solving the problem, you may attempt to solve only a portion of the test data.

The data scale and features for each test point are shown in the following table:

The abbreviated columns have the following meanings:

1. All Facing Inward: If marked "√", it indicates that the test point guarantees all toy figures face inward in the circle;
2. All Count Left: If marked "√", it indicates that the test point guarantees all instructions count to the left, i.e., for any 1 ≤ z ≤ m, ai = 0;
3. si = 1: If marked "√", it indicates that the test point guarantees all instructions count only 1, i.e., for any 1 ≤ z ≤ m, si = 1;
4. Occupation Length 1: If marked "√", it indicates that the test point guarantees all toy figures' occupations are strings of length 1.

</p>

Source

Adapted from NOIP2016-S Problem