0pts AHOI2006

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int cnt=0,rt;
struct Node
{
    int ls,rs;
    char val;
    int pri;
    int siz;
}t[N];
int newNode(int x)
{
    t[++cnt].siz=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].val=x;
    t[cnt].pri=rand();
    return cnt;
}
void update(int u)
{
    t[u].siz=t[t[u].ls].siz+t[t[u].rs].siz+1;
}
void Split(int u,int x,int &L,int &R)
{
    if(u==0)
    {
        L=R=0;
        return;
    } 
    if(t[t[u].ls].siz+1<=x)
    {
        L=u;
        Split(t[u].rs,x-t[t[u].ls].siz-1,t[u].rs,R);
    }
    else
    {
        R=u;
        Split(t[u].ls,x,L,t[u].ls);
    }
    update(u);
}
int Merge(int L,int R)
{
    if(L==0||R==0) return L+R;
    if(t[L].pri>t[R].pri)
    {
        t[L].rs=Merge(t[L].rs,R);
        update(L);
        return L;
    }
    else
    {
        t[R].ls=Merge(L,t[R].ls);
        update(R);
        return R;
    }
}
void print(int u)
{
    if(u==0) return;
    print(t[u].ls);
    cout<<t[u].val;
    print(t[u].rs);
}
int main()
{
    srand(time(NULL));
    int n;
    int len;
    int L,R;
    int p,pos=0;
    cin>>n;
    while(n--)
    {
        string op;
        cin>>op;
        if(op[0]=='M') cin>>pos;
        if(op[0]=='I')
        {
            cin>>len;
            Split(rt,pos,L,R);
            for(int i=1;i<=len;i++)
            {
                char c=getchar();
                while(c<32||c>126) c=getchar();
                L=Merge(L,newNode(c));
            }
            rt=Merge(L,R);
        }
        if(op[0]=='D')
        {
            cin>>len;
            Split(rt,pos+len,L,R);
            Split(L,pos,L,p);
            rt=Merge(L,R);
        }
        if(op[0]=='G')
        {
            cin>>len;
            Split(rt,pos+len,L,R);
            Split(L,pos,L,p);
            print(p);cout<<endl;
            rt=Merge(Merge(L,p),R);
        }
        if(op[0]=='R')
        {
            cin>>len;
            int x,y,z;
            Split(rt,1,x,y);
            Split(y,len,y,z);
            rt=Merge(x,z);
        }
        if(op[0]=='P') pos--;
        if(op[0]=='N') pos++; 
    }
    return 0;
}