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.

#include"cstdio"

#include"cstring"

#include"cmath"

#include"algorithm"

using namespace std;

const int MAXN=;

char str[MAXN*MAXN];

struct Block_List{

    int size,next;

    char s[*MAXN];

    Block_List()

    {

        memset(s,,sizeof(s));

        size=;

        next=-;

    }

    void push(char ch)

    {

        s[size++]=ch;

    }

    void insert(int pos,char ch)

    {

        for(int i=size;i>pos;i--)

        {

            s[i]=s[i-];

        }

        s[pos]=ch;

        size++;

    }

}bkl[MAXN];

int bsize,cnt,m;

void Init()

{

    gets(str);

    scanf("%d",&m);

    bsize=(int)sqrt(double(strlen(str)+m));

    for(int i=;str[i];i++)

    {

        if(bkl[cnt].size==bsize)

        {

            bkl[cnt].next=cnt+;

            cnt++;

        }

        bkl[cnt].push(str[i]);

    }

    cnt++;

}

void Update(int u)

{

    if(bkl[u].size<*bsize)    return ;

    /*

    for(int i=bsize;i<bkl[u].size;i++)

    {

        bkl[cnt].push(bkl[u].s[i]);

    }

    */

    strcpy(bkl[cnt].s,bkl[u].s+bsize);

    bkl[cnt].size=strlen(bkl[u].s)-bsize;

    bkl[u].size=bsize;

    bkl[cnt].next=bkl[u].next;

    bkl[u].next=cnt;

    cnt++;

}

void handle()

{

    int cas=;

    while(++cas<=m)

    {

        char op[];

        scanf("%s",op);

        if(op[]=='Q')

        {

            int pos;

            scanf("%d",&pos);

            int i;

            for(i=;pos>bkl[i].size;i=bkl[i].next)

            {

                pos-=bkl[i].size;

            }

            printf("%c\n",bkl[i].s[pos-]);

        }

        else

        {

            char ch[];

            int pos;

            scanf("%s%d",ch,&pos);

            int i;

            for(i=;pos>bkl[i].size&&bkl[i].next!=-;i=bkl[i].next)

            {

                pos-=bkl[i].size;

            }

            bkl[i].insert(pos-,ch[]);

            Update(i);

        }

    }

}

int main()

{

    Init();

    handle();

    return ;

}