#include<stdio.h>
#include<cstring>
#include<algorithm>
#define maxn 105
#define maxc 25
using namespace std;

int T,n,m;
char N[maxn][maxn],Sn[maxn][maxn],s[maxn],a[maxn][maxn];
int v[maxn][5*maxn],op[maxn],L[maxn],R[maxn],pos[maxn],nr[maxn];

int search1()
{
    for(int i=1;i<=m;i++)
     if(strcmp(Sn[i]+1,s+1)==0 || strcmp(N[i]+1,s+1)==0) return i;
    return 0;
}

int search2()
{
    for(int i=1;i<=m;i++)
     if(strcmp(N[i]+1,s+1)==0 || strcmp(Sn[i]+1,s+1)==0 || strcmp(a[i]+1,s+1)==0) return pos[i];
    return -1;
}

int main()
{
   //freopen("ticket.in","r",stdin);
    //freopen("ticket.out","w",stdout);

    int ind,ind2;
    scanf("%d%d\n",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s %s\n",N[i]+1,Sn[i]+1);
        pos[i]=-1;
        ind=strlen(N[i]+1);
        for(int j=1;j<=ind;j++)
         a[i][j]=N[i][j];
        a[i][ind+1]=' '; ind++;

        ind2=strlen(Sn[i]+1);
        for(int j=1;j<=ind2;j++)
         a[i][ind+j]=Sn[i][j];
        a[i][ind+ind2+1]='\0';
    }

    int type,x,y,aux;
    scanf("%d",&T);
    for(int it=1;it<=T;it++)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d",&x);
            if(op[x])
            {
                for(int i=L[x];i<=R[x];i++) pos[v[x][i]]=-1;
                op[x]=L[x]=R[x]=0;
            }
            else op[x]=1;
            continue;
        }
        if(type==2)
        {
            scanf("%d ",&x);
            scanf("%s\n",s+1);
            y=strlen(s+1);
            s[y+1]='\0';

            R[x]++; aux=search1(); v[x][R[x]]=aux;
            if(R[x]==1) L[x]=1;
            pos[aux]=x;
            continue;
        }
        if(type==3)
        {
            scanf("%d",&x);
            pos[v[x][L[x]]]=-1; L[x]++;
            continue;
        }
        if(type==4)
        {
            scanf("%d",&x);
            if(!op[x] || L[x]>R[x]) printf("-1\n");
            else
            {
                for(int i=R[x];i>=L[x];i--)
                printf("%s %s ",N[i]+1,Sn[i]+1);
                printf("\n");
            }
            continue;
        }
        scanf(" ");
        fgets(s+1,sizeof(s),stdin);
        y=strlen(s+1)-1;

        s[y+1]='\0';
        printf("%d\n",search2());
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}