#include <iostream>
#include <cstring>
#include <string>
#include <deque>
using namespace std;
int x,a[105],i,n,m,q,op;
char nn[45];
string num,prenum;
struct structu
{
    string numele,prenumele;
}numele[105],aux;
deque <pair<string,string> >Q[105];
void schimba()
{
    cin>>x;
    a[x]=!a[x];
    Q[x].clear();
}
void adauga()
{
    cin>>x;
    cin>>num;
    for(i=1;i<=n;i++)
    {
        if(numele[i].numele==num||numele[i].prenumele==num)
            break;
    }
    Q[x].push_back(make_pair(numele[i].numele,numele[i].prenumele));
}
void scoate()
{
    cin>>x;
    Q[x].pop_front();
}
void afiseaza()
{
    cin>>x;
    if(Q[x].empty())
    {
        cout<<"-1\n";
        return;
    }
    for(deque <pair<string,string> >::iterator it=Q[x].end()-1;it>=Q[x].begin();it--)
        cout<<it->first<<' '<<it->second<<" ";
    cout<<'\n';
}
void cauta()
{
    cin>>num;
    for(i=1;i<=n;i++)
    {
        for(deque <pair<string,string> >::iterator it=Q[i].begin();it!=Q[i].end();it++)
        {
            if(it->first==num||it->second==num)
            {
                cout<<i<<"\n";
                return;
            }
        }
    }
    cout<<"-1\n";
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>num>>prenum;
        numele[i].numele=num;
        numele[i].prenumele=prenum;
    }
    cin>>q;
    for(;q;q--)
    {
        cin>>op;
        switch(op)
        {
            case 1:{schimba();break;}
            case 2:{adauga();break;}
            case 3:{scoate();break;}
            case 4:{afiseaza();break;}
            case 5:{cauta();break;}
        }
    }
    return 0;
}