1004

#include <stdio.h>
#include <stdlib.h>
int st[10001][2],ans[10001],ians=0;
int Nc,Ns,inst,last=1,first=1;
struct asdf
{
    int index;
    int room;
    int id;
    int rear;
} data[10001];
int findcs(int cs)
{
    int i=last,ck=1;
    while(data[i].index!=-1 || data[i].room==cs)
    {
        if(data[i].room==cs)
        {
            ck=2;
            break;
        }
        i=data[i].index;
    }
    if(ck==2) return i;
    else return -1;
}
int main()
{
    int i,j,run,ck,cs;
    int inn=0,out=0;
    int node=1;
    char in;
    scanf("%d%d",&Nc,&Ns);
    for(i=0; i<Ns; i++) scanf("%d %d",&st[i][0],&st[i][1]);
    while(1)
    {
        scanf(" %c",&in);
        if(in=='E')
        {
            inn++;
            scanf("%d",&inst);
            i=0;
            while(st[i][1]!=inst) i++;
            cs=st[i][0];
            if(first==node)
            {
                data[first].id=inst;
                data[first].index=-1;
                data[first].rear=-1;
                data[first].room=cs;
                node++;
            }
            else
            {
                ck=findcs(cs);
                int renode;
                if(ck>0)
                {
                    renode=data[ck].rear;
                    data[node].id=inst;
                    data[node].index=ck;
                    data[node].room=cs;
                    data[node].rear=renode;
                    if(renode>0)
                    {
                        data[renode].index=node;
                        data[ck].rear=node;
                    }
                    else
                    {
                        data[ck].rear=node;
                        last=node;
                    }
                    node++;
                }
                else
                {
                    data[node].id=inst;
                    data[node].index=last;
                    data[node].rear=-1;
                    data[node].room=cs;
                    data[last].rear=node;
                    last=node;
                    node++;
                }
            }
        }
        else if(in=='D')
        {
            if(inn==out)
            {
                printf("empty\n");
                int j;
                for(j=0;j<ians;j++) printf("%d\n",ans[j]);
            }
            else
            {
                out++;
                int temp;
                printf("%d\n",data[first].id);
                ans[ians]=data[first].id;
                ians++;
                temp=data[first].rear;
                data[first].rear=-1;
                first=temp;
                data[first].index=-1;
            }
        }
        else
        {
            printf("0\n");
            return 0;
        }
    }
    return 0;
}