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

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.

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