#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
int i,t,m,n,a,j,B[101],M[101][101],x;
char Nume[101][21],Prenume[101][21],Num[101];
bool V[101];
int main()
{
   // freopen("ticket.in","r",stdin);
   // freopen("ticket.out","w",stdout);
    cin>>n>>m;
    for (i=1;i<=m;i++)
        cin>>Nume[i]>>Prenume[i];
    cin>>t;
    for (i=1;i<=t;i++)
    {
        cin>>a;
        if (a==1)
         {cin>>x; V[x]=true;}
        else if (a==2)
            {cin>>x>>Num;
             for (j=1;j<=m;j++) if (strcmp(Num,Prenume[j])==0||strcmp(Num,Nume[j])==0) break;
                M[x][0]++;
                M[x][M[x][0]]=j;
                B[j]=x;
            }
        else if (a==3)
        {
            cin>>x;
            B[M[x][1]]=0;
            for (j=2;j<=M[x][0];j++) M[x][j-1]=M[x][j];
            M[x][M[x][0]]=0;
            M[x][0]--;
        }
        else if (a==4)
        {
            cin>>x;
            if (M[x][0]==0) cout<<-1;
            else for (j=M[x][0];j>=1;j--) cout<<Nume[M[x][j]]<<" "<<Prenume[M[x][j]]<<" ";
            cout<<'\n';
        }
        else if (a==5)
        {
            cin>>Num;
            for (j=m;j>=1;j--) if (strcmp(Num,Nume[j])==0||strcmp(Num,Nume[j])==0) break;
            if (B[j]!=0) cout<<B[j];
            else cout<<-1;
            cout<<'\n';
        }
    }
}