Big String

Time Limit: 1000MS

Memory Limit: 131072K

Description

You are given a string and supposed to do some string manipulations.

Input

The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000.The second line contains the number of manipulation commands N (0 < N 2,000). The following N lines describe a command each. The commands are in one of the two formats below:
  1. I ch p: Insert a character ch before the p-th character of the current string. If p is larger than the length of the string, the character is appended to the end of the string.
  2. Q p: Query the p-th character of the current string. The input ensures that the p-th character exists.
All characters in the input are digits or lowercase letters of the English alphabet.

Output

For each Q command output one line containing only the single character queried.

Sample Input

ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3

Sample Output

a
d
e

Hint

Source

POJ Monthly--2006.07.30, zhucheng

提交代码