#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define MAXN 105

int N, M, T, x, t;
vector<pair<string, string> > P;
vector<int> S[MAXN];
bool open[MAXN];
int cIdx[MAXN];

int calcIdx(string &s) {
    for(int i = 0; i < M; i++)
        if(s == P[i].first || s == P[i].second)
            return i;
    throw new exception();
    return -1;
}

int main() {
//	freopen("date.in", "r", stdin);
//	freopen("date.out","w", stdout);
	
	cin >> N >> M;
	string name, surname;
	for(int i = 0; i < M; i++) {
        cin >> name >> surname;
        P.push_back(make_pair(name, surname));
	}
	
	fill(cIdx, cIdx + M, -1);
	
	cin >> T;
	while(T--) {
        cin >> t;
        if(t == 1) {
            cin >> x;
            if(open[x]) {
                for(vector<int> :: iterator it = S[x].begin(); it != S[x].end(); it++)
                    cIdx[*it] = -1;
                S[x].clear();
            }
            open[x] = !open[x];
        }
        else if(t == 2) {
            cin >> x >> name;
            int idx = calcIdx(name);
            S[x].push_back(idx);
            cIdx[idx] = x;
        }
        else if(t == 3) {
            cin >> x;
            int idx = *(S[x].begin());
            cIdx[idx] = -1;
            S[x].erase(S[x].begin());
        }
        else if(t == 4) {
            cin >> x;
            if(S[x].size() == 0)
                cout << -1 << '\n';
            else {
                bool first = true;
                for(vector<int> :: reverse_iterator it = S[x].rbegin(); it != S[x].rend(); it++) {
                    if(!first)
                        cout << ' ';
                    first = false;
                    cout << P[*it].first << ' ' << P[*it].second;
                }
                cout << '\n';
            }
        }
        else if(t == 5) {
            cin >> name;
            int idx = calcIdx(name);
            cout << cIdx[idx] << '\n';
        }
	}
	
	return 0;
}