L. String Doubling
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have an initial string $$$S$$$, and $$$q$$$ operations will be performed sequentially. There are three types of operations:

  1. Add Character: Append a given character $$$c$$$ to the end of the string.
  2. Delete from End: Delete $$$k$$$ characters from the end of the string. If $$$k$$$ is greater than the current length of the string, clear the entire string.
  3. Copy and Concatenate: Make a copy of the current string and append it to the original string (i.e., new string = original string + original string).

After all operations are completed, you need to answer: what is the $$$P$$$-th character of the final string? The indices start from $$$1$$$. It is guaranteed that $$$P$$$ does not exceed the length of the final string.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, denoting the number of test cases.

For each test case:

  • The first line contains a string $$$S$$$ $$$(1 \le |S| \le 2 \times 10^5)$$$, representing the initial string. $$$S$$$ consists of lowercase English letters only.
  • The second line contains an integer $$$q$$$ $$$(0 \le q \le 2 \times 10^5)$$$, denoting the number of operations.
  • The next $$$q$$$ lines describe the operations:
    • 1 c: Append a character $$$c$$$ to the end ($$$c$$$ is a lowercase English letter).
    • 2 k: Delete $$$k$$$ characters from the end, where $$$1 \le k \le 10^9$$$.
    • 3: Make a copy of the current string and concatenate it to the end.
  • The last line contains an integer $$$P$$$ $$$(1 \le P \le 10^{18})$$$, representing the queried position.

Guarantees: The sum of $$$|S|$$$ across all test cases does not exceed $$$2 \times 10^5$$$, and the sum of $$$q$$$ across all test cases does not exceed $$$2 \times 10^5$$$. For each test case, the length of the string after all operations is at least $$$P$$$.

Output

For each test case, output a single character on a line, which is the $$$P$$$-th character of the final string.

Example
Input
1
ab
3
1 c
3
2 1
4
Output
a