#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <queue>

using namespace std;

ifstream f("date.in");
#define f cin

int n, m;
bool cnt[105];
pair<string, string> name[105]; int pozin[105];
map<string, int> mp;
int q[105][1000], st[105], dr[105];
string s;

void change()
{
    int x;
    f >> x;

    if (cnt[x] == false) {
        cnt[x] = true;
        return ;
    }

    cnt[x] = false;
    for (int i = st[x]; i <= dr[x]; i++) {
        pozin[q[x][i]] = 0;
    }
    dr[x] = 0; st[x] = 0;
}

void addQue()
{
    int x;
    string str;
    f >> x >> str;

    int poz = mp[str];
    q[x][dr[x]] = poz; dr[x]++;
    pozin[poz] = x;
}

void leaveQue()
{
    int x;
    f >> x;
    pozin[q[x][st[x]]] = 0;
    st[x]++;
}

void printNames()
{
    int x;
    f >> x;

    if (st[x] >= dr[x]) {
        cout << -1 << '\n';
        return ;
    }

    for (int i = dr[x] - 1; i >= st[x]; i--) {
        int poz = q[x][i];
        cout << name[poz].first << ' ' << name[poz].second << ' ';
    }
    cout << '\n';
}

void printIdx()
{
    string str;
    f >> str;
    int poz = mp[str];

    if (pozin[poz] == 0) {
        cout << -1 << '\n';
    } else {
        cout << pozin[poz] << '\n';
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> name[i].first >> name[i].second;
        mp[name[i].first] = i;
        mp[name[i].second] = i;
    }

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

        switch (op) {
            case 1: change(); break;
            case 2: addQue(); break;
            case 3: leaveQue(); break;
            case 4: printNames(); break;
            case 5: printIdx(); break;
        }
    }

    return 0;
}