#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <time.h>
#include <stdlib.h>
#define mod 1000003
#define inf 9999999
using namespace std;
/* Treaps *\*/
struct lista { int key,pos,priority; lista *left,*right;
       lista(){
       key=0; pos=0; priority=0; left=NULL; right=NULL;
       }
};
int n,k,i,j,x,y;
lista *root,*nil,*curent_treap,*Ts,*Td,*Tf;
char c;
void rotleft(lista *&a)
{
    lista *aux=a->left;
    a->left=aux->right; aux->right=a;
    a=aux;
}
void rotright(lista *&a)
{
    lista *aux=a->right;
    a->right=aux->left; aux->left=a;
    a=aux;
}
void balance(lista *&a)
{
    if (a->left->priority>a->priority) rotleft(a); else
    if (a->right->priority>a->priority) rotright(a);
}
inline void insert_into_tree(lista *&a,int key,int pos,int priority)
{
    if (a==nil){
        a=new lista; a->key=key; a->pos=pos; a->priority=priority;
        a->left=nil; a->right=nil;
        return;
    }
    if (pos<a->pos) insert_into_tree(a->left,key,pos,priority); else
        insert_into_tree(a->right,key,pos,priority);
    balance(a);
}
inline int find_component(lista *&a,int pos)
{
    if (a==nil) return 0;
    if (a->pos==pos) return (a->key);
    if (pos<a->pos) return(find_component(a->left,pos)); else
        return (find_component(a->right,pos));
}
inline void split(lista *&curent_treap,int pos,lista* &Ts,lista* &Td)
{
    insert_into_tree(curent_treap,0,pos,inf); Ts=nil; Td=nil;
    Ts=curent_treap->left; Td=curent_treap->right;
    delete curent_treap;
}
inline void remove_component(lista *&a,int key)
{
    if (key<a->key) remove_component(a->left,key); else
    if (key>a->key) remove_component(a->right,key); else {
    if (a->left==nil && a->right==nil) {
            delete(a); a=nil; return;
    } else
     {
        if (a->left->priority>a->right->priority) rotleft(a); else
            rotright(a);
        remove_component(a,key);
     }
    }
}
inline void join(lista *&b,lista *&Ts,lista *&Td)
{
    b=new lista; b->key=-3; b->priority=-5;
    b->left=Ts; b->right=Td;
    remove_component(b,-3);
}
int main(){
freopen("secv8.in","r",stdin);
freopen("secv8.out","w",stdout);
scanf("%d%d\n",&n,&k); srand(unsigned(time(0)));
nil=new lista; root=nil;
for (i=1;i<=n;i++){
    scanf("%c",&c);
    switch (c){
        case 'I':{ scanf("%d %d",&x,&y);
            insert_into_tree(root,y,x,(rand()%mod)+1); break;
        }
        case 'A':{ scanf("%d",&x); printf("%d\n",find_component(root,x)); break; }
        case 'D':{ scanf("%d %d",&x,&y); curent_treap=root; split(curent_treap,x-1,Ts,Td);
                   curent_treap=root; split(curent_treap,y+1,Td,Tf); join(root,Ts,Tf);
        }
    }
    scanf("\n");
}
return 0;
}