#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<fstream>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

using namespace std;

int N,M,T;
int Que[105];
bool P[105];
char Prenume[105][30],Nume[105][30];
deque<int> Q[105];

int main()
{
    int i,x,p,t;
    char name[30];
    deque<int>::reverse_iterator it;
    deque<int>::iterator jt;

    scanf("%d%d",&N,&M);

    for(i=1; i<=M; i++)
    {
        scanf("%s%s",Prenume[i],Nume[i]);
        Que[i]=-1;
    }

    scanf("%d",&T);

    for(; T; --T)
    {
        scanf("%d",&t);
        if(t==1)
        {
            scanf("%d",&x);
            P[x]^=1;
            if(!P[x])
            {
                for(it=Q[x].rbegin(); it!=Q[x].rend(); it++)
                    Que[*it]=-1;
                Q[x].clear();
            }
            continue;
        }
        if(t==2)
        {
            scanf("%d%s",&x,name);
            for(i=1; i<=M; i++)
                if(strcmp(name,Nume[i])==0 || strcmp(name,Prenume[i])==0) break;
            if(Que[i]!=-1)
            {
                t=Que[i];
                for(jt=Q[t].begin(); jt!=Q[t].end(); jt++)
                    if(*jt==i) break;
                Q[t].erase(jt);
            }
            Q[x].push_back(i);
            Que[i]=x;
            continue;
        }
        if(t==3)
        {
            scanf("%d",&x);
            Que[Q[x].front()]=-1;
            Q[x].pop_front();
            continue;
        }
        if(t==4)
        {
            scanf("%d",&x);
            p=Q[x].size();
            if(p==0)
            {
                printf("-1\n");
                continue;
            }
            for(it=Q[x].rbegin(); it!=Q[x].rend(); it++)
                printf("%s %s ",Prenume[*it],Nume[*it]);
            printf("\n");
            continue;
        }
        if(t==5)
        {
            scanf("%s",name);
            for(i=1; i<=M; i++)
                if(strcmp(name,Nume[i])==0 || strcmp(name,Prenume[i])==0) break;
            printf("%d\n",Que[i]);
            continue;
        }
    }

    return 0;
}