#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <deque>

using namespace std;

int N, M, T;
string S1[102], S2[102];
map<string, int> W;
bool is[102];
int whn[102];
deque<int> Q[102];

int main()
{
	cin.sync_with_stdio(false);
	
	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
		whn[i] = -1;
	for (int i = 1; i <= M; ++i)
	{
		string s1, s2;
		cin >> s1 >> s2;
		S1[i] = s1;
		S2[i] = s2;
		W[s1] = i;
		W[s2] = i;
	}
	cin >> T;
	for (int i = 1, type; i <= T; ++i)
	{
		cin >> type;
		if (type == 1)
		{
			int wh;
			cin >> wh;
			
			is[wh] = !is[wh];
			
			if (!is[wh])
			{
				while (!Q[wh].empty())
				{
					whn[Q[wh].front()] = -1;
					Q[wh].pop_front();
				}
			}
		}
		else if (type == 2)
		{
			int wh;
			string s;
			
			cin >> wh >> s;
			Q[wh].push_back(W[s]);
			whn[W[s]] = wh;
		}
		else if (type == 3)
		{
			int wh;
			cin >> wh;
			
			if (!Q[wh].empty())
			{
				whn[Q[wh].front()] = -1;
				Q[wh].pop_front();
			}
		}
		else if (type == 4)
		{
			int wh;
			cin >> wh;
			for (int j = int(Q[wh].size()) - 1; j >= 0; --j)
				cout << S1[Q[wh][j]] << ' ' << S2[Q[wh][j]] << ' ';
			if (Q[wh].empty())
				cout << -1;
			cout << '\n';
		}
		else if (type == 5)
		{
			string s;
			cin >> s;
			
			cout << whn[W[s]] << '\n';
		}
	}
}