#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) { a->key=key; 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=curent_treap->left; Td=curent_treap->right;
    delete curent_treap;
}
inline void remove_component(lista* &a)
{
    if (a->left==nil && a->left==nil) { delete(a); a=nil; return; } else
    {
        if (a->left->priority>a->right->priority) rotleft(a); else rotright(a);
        remove_component(a);
    }
}
inline void join(lista* &root,lista* &Ts,lista* &Td)
{
    root=new lista; root->pos=0; root->key=0;
    root->left=Ts; root->right=Td;
    remove_component(root);
}
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(root,x,Ts,Td); split(root,y,Td,Tf); join(root,Ts,Tf);
        }
    }
    scanf("\n");
}
return 0;
}