#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
#include <fstream>
#include <bitset>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <utility>
#include <string>
#include <iomanip>
#include <cstring>
#include <cmath>

#define vint vector<int>::iterator
#define vintp vector<pair<int,int> >::iterator
#define ll long long
#define maxn 251
#define mod 329885391853LL

using namespace std;

ifstream fin ("A.in");
ofstream fout("A.out");

string name[201],surname[201];
map <string,int> M,MM;
int q[201][201];
int st[201],l[201]; int state[201];
int wh[201],n,m,t,op,x;
string N;

int main()
{
    cin>>n>>m;

    for (int i=1; i<=n; ++i)
        st[i] = 1;

    for (int i=1; i<=m; ++i)
    {
        cin>>name[i]>>surname[i];

        M.insert (make_pair(name[i],i));
        MM.insert (make_pair(surname[i],i));
    }

    cin>>t;

    for (int i=1; i<=t; ++i)
    {
        cin>>op;

        if (op == 1)
        {
            cin>>x;

            state[x] = 1 - state[x];

            if (state[x] == 0)
            {
                for (int j=st[x]; j<=l[x]; ++j)
                    wh[q[x][j]] = 0;

                st[x] = l[x] + 1;
            }
        }

        else if (op == 2)
        {
            cin>>x>>N;

            map<string,int>::iterator it = M.find(N);

            if (it != M.end())
            {
                q[x][++l[x]] = it->second;
                wh[it->second] = x;
            }
            else
            {
                it = MM.find(N);
                q[x][++l[x]] = it->second;
                wh[it->second] = x;
            }
        }

        else if (op == 3)
        {
            cin>>x;
            wh[q[x][st[x]]]= 0;
            ++st[x];
        }

        else if (op == 4)
        {
            cin>>x;

            if (st[x] > l[x])
              cout<<-1;
              else {for (int j = l[x]; j > st[x]; --j)
               {
                cout<<name[q[x][j]]<<" "<<surname[q[x][j]]<<" ";
               }
                cout<<name[q[x][st[x]]]<<" "<<surname[q[x][st[x]]];}
              cout<<"\n";
        }

        else
        {
            cin>>N;

            map<string,int>::iterator it = M.find(N);

            if (it != M.end())
            {
                x = it->second;
            }
            else
            {
                it = MM.find(N);
                x = it->second;
            }

            if (wh[x] == 0)
                cout<<-1;
            else cout<<wh[x];
            cout<<"\n";
        }
    }
}