Problem F: String operations

Problem F: String operations

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1372  Solved: 255
[Submit][Status][Web Board]

Description

Psy has a string S and "String Master" Peggy orders him to do the following two operations:

Insert(ch, p), means inserting the char ch to position p.

Find(p), means finding the char at position p and print it to screen.

Since Psy is poor at solving string problem, he asks you for help. Can you help him?

Input

The first line will be an integer T (1 <= T <= 10), which is the number of test cases.

For each test case, the first line will be a string S (base 1) consisting of lowercases which psy has. The second line will be an integer n, which is the number of operations. Then there will be n lines operations. To simplify the problem, we use 1 represents operation Insert and 2 represents operation Find. ( len(S) <= 200000, n <= 10000)

Output

For each test case, follow the operation the problem gives.

Sample Input

1
madamimadam
4
1 h 1
1 h 2
2 3
2 2

Sample Output

m
h

HINT

In the sample case, after the first operation insert, the string becomes 'hmadamimadam'. After the second operation insert, the string becomes 'hhmadamimadam'. So we can find the thid char is 'm' and the second char is 'h'.

[Submit][Status]