#include <stdio.h>
#include <string.h>
#include <vector>

#define NMAX 105

using namespace std;

struct person{char nume[25],prenume[25];int statie;bool ok;};
vector<int> Q[NMAX*5];
bool STATUS[NMAX];

person P[NMAX];

int N,M,T;

void read()
{
    scanf("%d %d\n",&N,&M);

    for (int i=1;i<=M;i++)
    {
        scanf("%s ",P[i].prenume);
        scanf("%s\n",P[i].nume);
    }

}

int find(char a[25])
{
    int len2=strlen(a);

    for (int i=1;i<=M;i++)
    {
        int len,ok=1;

        len=strlen(P[i].nume);
        if (len==len2)
            {for (int j=0;j<len;j++)
                if (P[i].nume[j]!=a[j])
                {
                    ok=0;
                    j=len+1;
                }}
        else ok=0;
        if (ok) return i;

        ok=1;
        len=strlen(P[i].prenume);
        if (len==len2)
            for (int j=0;j<len;j++)
                {if (P[i].prenume[j]!=a[j])
                {
                    ok=0;
                    j=len+1;
                }}
        else ok=0;
        if (ok) return i;
    }

    return 0;

}

void query4(int nr)
{
    for (int i=Q[nr].size()-1;i>=0;i--)
        if (Q[nr][i]<=N && Q[nr][i]>=1)
            if (!P[Q[nr][i]].ok)
                printf("%s %s ",P[Q[nr][i]].prenume,P[Q[nr][i]].nume);
}

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

    read();
    scanf("%d\n",&T);
    for (int i=1;i<=T;i++)
    {
        int type,nr;
        char a[25];

        scanf("%d ",&type);
        if (type==1)
        {
            scanf("%d\n",&nr);
            if (STATUS[nr]) {STATUS[nr]=0; Q[nr].clear();}
            else STATUS[nr]=1;
        }
        if (type==2)
        {
            scanf("%d ",&nr);
            scanf("%s\n",a);
            if (find(a))
            {
                Q[nr].push_back(find(a));
                P[find(a)].statie=nr;
            }
        }
        if (type==3)
        {
            scanf("%d ",&nr);
            P[Q[nr][0]].ok=1;
        }
        if (type==4)
        {
            scanf("%d ",&nr);
            query4(nr);
            printf("\n");
        }
        if (type==5)
        {
            scanf("%s ",a);
            if (!find(a)) printf("-1\n");
            else
            {
                if (!P[find(a)].statie) printf("-1\n");
                else
                    if (!P[find(a)].ok)
                        printf("%d\n",P[find(a)].statie);
                    else
                        if (P[find(a)].ok) printf("-1\n");
            }
        }
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}