#include <bits/stdc++.h>
using namespace std;
int main(){

    int nc,ns;
    scanf("%d %d",&nc,&ns);
    int c[ns],s[ns];
    for(int i=0;i<ns;i++){
        scanf("%d %d",&c[i],&s[i]);
    }

    vector <int> v,k;
    bool check=true;
    while(check){
        char a;
        scanf(" %c",&a);
        if(a=='X'){
            check=false;
            break;
        }
        else if( a=='D' && v.size()>0){//print->erase
            printf("%d\n",v[0]);
            v.erase(v.begin()+0);
            k.erase(k.begin()+0);
        }
        else if( a=='E'){
            int num,cls;//cls=class
            scanf("%d",&num);

            //find class
            for(int i=0;i<ns;i++){
                if(s[i]==num && c[i]!=0){cls=c[i];c[i]=0;}
            }

            //in line
            if(v.size()==0) {
                v.push_back(num);
                k.push_back(cls);
            }
            else {
                for(int i=0;i<v.size();i++){
                    if(k[i]==cls && k[i+1]!=cls){//insert
                        v.insert(v.begin()+i+1,num);
                        k.insert(k.begin()+i+1,cls);
                        break;
                    }
                    else if(i==k.size()-1){
                        v.push_back(num);
                        k.push_back(cls);
                        break;
                    }
                }
            }
        }
    }

    printf("0");

    return 0;
}