#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
int tip,n,m,T,i,j,k,l1[109],l2[109],l,open[109];
char s1[109][109],s2[109][109],sir[109];
vector < int > v[109];
struct nod
{
    nod *urm[52];
    int poz;
    nod()
    {
        poz=0;
        memset(urm,0,sizeof(urm));
    }
}*q,*R;
int cod(char x)
{
    if(x>='a'&&x<='z') return x-'a';
    return 'z'-'a'+1+x-'A';
}
void afis(int poz)
{
    int i;
    for(i=1;i<=l1[poz];i++)
        printf("%c",s1[poz][i]);
    printf(" ");
    for(i=1;i<=l2[poz];i++)
        printf("%c",s2[poz][i]);
}
int Get()
{
    int j;
    q=R;
    for(j=1;j<=l;j++)
        q=q->urm[cod(sir[j])];
    return q->poz;
}
int main()
{
//freopen("input","r",stdin);
//freopen("output","w",stdout);
scanf("%d%d\n",&n,&m);
R=new nod;
for(i=1;i<=m;i++)
{
    scanf("%s ",s1[i]+1);
    gets(s2[i]+1);
    l1[i]=strlen(s1[i]+1);
    l2[i]=strlen(s2[i]+1);
    q=R;
    for(j=1;j<=l1[i];j++)
    {
        if(q->urm[cod(s1[i][j])]==0) q->urm[cod(s1[i][j])]=new nod;
        q=q->urm[cod(s1[i][j])];
    }
    q->poz=i;
    q=R;
    for(j=1;j<=l2[i];j++)
    {
        if(q->urm[cod(s2[i][j])]==0) q->urm[cod(s2[i][j])]=new nod;
        q=q->urm[cod(s2[i][j])];
    }
    q->poz=i;
}
scanf("%d\n",&T);
while(T)
{
    T--;
    scanf("%d ",&tip);
    if(tip==1)
    {
        scanf("%d\n",&i);
        open[i]^=1;
        if(open[i]==0) v[i].clear();
    }
    else
    if(tip==2)
    {
        scanf("%d ",&i);
        gets(sir+1);
        l=strlen(sir+1);
        v[i].push_back(Get());
    }
    else
    if(tip==3)
    {
        scanf("%d\n",&i);
        if(!v[i].empty()) v[i].erase(v[i].begin());
    }
    else
    if(tip==4)
    {
        scanf("%d\n",&i);
        if(v[i].empty())
        {
            printf("-1\n");
            continue;
        }
        for(j=v[i].size()-1;j>=0;j--)
        {
            afis(v[i][j]);
            if(j>0) printf(" ");
        }
        printf("\n");
    }
    else
    {
        gets(sir+1);
        l=strlen(sir+1);
        i=Get();
        for(j=1;j<=n;j++)
        {
            for(k=0;k<v[j].size();k++)
                if(v[j][k]==i) break;
            if(k<v[j].size()) break;
        }
        if(j<=n) printf("%d\n",j);
        else printf("-1\n");
    }
}
return 0;
}