#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

#define inf 2000000

long n, i, j, k, t, el, poz, p1, p2;
char ch;
struct treap
{
    long din, key, rev, pr;
    treap *left, *right;
} *nil, *rad, *n1, *n2, *n3;

void dinamica(treap *nod)
{
    nod->din=(nod->left)->din+(nod->right)->din+1;
}

treap *r_left(treap *nod)
{
    treap *aux=nod->left;
    nod->left=(nod->left)->right;
    dinamica(nod);
    aux->right=nod;
    dinamica(aux);
    return aux;
}

treap *r_right(treap *nod)
{
    treap *aux=nod->right;
    nod->right=(nod->right)->left;
    dinamica(nod);
    aux->left=nod;
    dinamica(aux);
    return aux;
}

treap *balans(treap *nod)
{
    if((nod->left)->pr>nod->pr)
        return r_left(nod);
    if((nod->right)->pr>nod->pr)
        return r_right(nod);
    return nod;
}

treap *insert(treap *nod, long ky, long poz, long pr)
{
    if(nod==nil)
    {
        treap *aux;
        aux=new treap;
        aux->left=nil;
        aux->right=nil;
        aux->key=ky;
        aux->pr=pr;
        aux->din=1;
        return aux;
    }
    if(poz<=nod->left->din+1)
        nod->left=insert(nod->left, ky, poz, pr);
    else
        nod->right=insert(nod->right, ky, poz-nod->left->din-1, pr);
    nod=balans(nod);
    dinamica(nod);
    return nod;
}

long querry(long cat, treap *nod)
{
    if(nod->left->din==cat-1)
        return nod->key;
    if(nod->left->din<cat)
        return querry(cat-(nod->left->din)-1, nod->right);
    return querry(cat, nod->left);
}

treap *sterge(treap *nod)
{
    if(nod->left==nil && nod->right==nil)
    {
        delete nod;
        nod=nil;
        return nod;
    }
    if(nod->left->pr>nod->right->pr)
    {
        nod=r_left(nod);
        nod->right=sterge(nod->right);
    }
    else
    {
        nod=r_right(nod);
        nod->left=sterge(nod->left);
    }
    dinamica(nod);
    return nod;
}

treap *join(treap *a, treap *b)
{
    treap *aux=nil;
    aux->left=a;
    aux->right=b;
   // printf("*%d %d\n", aux->left->pr, aux->right->pr);
    return sterge(aux);
}

void split(long p1, long p2)
{
    n1=n2=n3=nil;
    rad=insert(rad, 0, p1, inf);
    n1=rad->left;
    rad=rad->right;
  //  printf("*%d\n", rad->key);
    rad=insert(rad, 0, p2-p1+2, inf);
    n2=rad->left;
    n3=rad->right;
}        

int main()
{
    srand(time(0));
    freopen("secv8.in", "r", stdin);
    freopen("secv8.out", "w", stdout);
    scanf("%d%d\n", &t, &k);
    if(k==1) return 0;
    nil=new treap;
    nil->left=NULL;
    nil->right=NULL;
    nil->din=0;
    nil->pr=0;
    rad=nil;
    while(t--)
    {
        scanf("%c", &ch);
        if(ch=='I')
        {
            scanf("%d%d\n", &el, &poz);
            rad=insert(rad, el, poz, rand()%1000000+1);
        }
        if(ch=='A')
        {
            scanf("%d\n", &poz);
            printf("%d\n", querry(poz, rad));
        }
        if(ch=='D')
        {
            scanf("%d%d\n", &p1, &p2);
            split(p1, p2);
            rad=join(n1, n3);
          //  printf("%d %d %d\n", rad->key, rad->left->key, rad->right->key);
         //   printf("%d %d %d\n", rad->din, rad->left->din, rad->right->din);
        }        
    }
    return 0;
}