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

using namespace std;

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

int main()
{
	cin.sync_with_stdio(false);
	
	cin >> N >> M;
	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];
			
				while (!Q[wh].empty())
					Q[wh].pop_front();
		}
		else if (type == 2)
		{
			int wh;
			string s;
			
			cin >> wh >> s;
			Q[wh].push_back(W[s]);
		}
		else if (type == 3)
		{
			int wh;
			cin >> wh;
			
			if (!Q[wh].empty())
				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;
			
			int now = W[s];
			
			bool any = false;
			for (int j = 1; j <= N; ++j)
			{
				bool here = false;
				for (int k = 0; k < int(Q[j].size()); ++k)
					if (Q[j][k] == now)
					{
						here = true;
						break;
					}
				if (here)
				{
					any = true;
					cout << j << '\n';
					break;
				}
			}
			
			if (!any) cout << -1 << '\n';
		}
	}
}