#include<fstream>
#include<iostream>
#include<string>
#include<map>
#include<cmath>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<cstring>
#include<climits>
#include<deque>
#include<stack>

#define JUDGE

using namespace std;

int N, M, T;

map <string, int> MAP;
vector <int> people;
vector <string> names;
vector <deque <int> > ques;
vector <int> states;

int main() {
#ifndef JUDGE
	freopen("input.txt", "r", stdin);
#endif
	int i;
	string name, surname;
	cin >> N >> M;
	states.resize(N + 1);
	ques.resize(N + 1);
	people.resize(M + 1);
	names.resize(M + 1);
	for (i = 0; i < M; ++i) {
		cin >> name >> surname;
		people[i + 1] = 0;
		names[i + 1] = name + " " + surname;
		MAP.insert(make_pair(name, i + 1));
		MAP.insert(make_pair(surname, i + 1));
	}
	cin >> T;
	int t, x, j = 0;
	for (i = 1; i <= T; ++i) {
		cin >> t;
		if (t == 1) {
			cin >> x;
			if (states[x] == 0) {
				states[x] = 1; ques[x].clear();
			}
			else {
				states[x] = 0;
				for (j = ques[x].size() - 1; j >= 0; --j) {
					people[ques[x][j]] = 0;
				}
				ques[x].clear();
			}
		}
		if (t == 2) {
			cin >> x; cin >> name;
			int pos = MAP[name];
			people[pos] = x;
			ques[x].push_back(pos);
		}
		if (t == 3) {
			cin >> x;
			if (ques[x].size() != 0) {
				int poz = ques[x].front();
				people[poz] = 0;
				ques[x].pop_front();
			}
		}
		if (t == 4) {
			cin >> x;
			if (ques[x].empty() || states[x] == 0) {
				cout << -1;
			}
			else {
				for (j = ques[x].size() - 1; j >= 0; --j) {
					int y = ques[x][j];
					cout << names[y] << ' ';
				}
			}
			cout << '\n';
		}
		if (t == 5) {
			cin >> name;
			int pos = MAP[name];
			if (people[pos] == 0) cout << -1;
				else cout << people[pos];
			cout << '\n';
		}
	}
#ifndef JUDGE
	while (1);
#endif
	return 0;
}