#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<iostream>
#include<bitset>
#include<string>

using namespace std;

int n,m;
int front[105];
vector< string >G[105];
map<string,string>M1,M2;

int main () {
	
	#ifndef ONLINE_JUDGE
	freopen("mindcoding3.in","r",stdin);
	freopen("mindcoding3.out","w",stdout);
	#endif
	
	cin >> n >> m;
	for ( int i = 1 ; i <= m ; ++i ){
		string s1,s2;
		cin >> s1 >> s2;
		M1[s1] = s2; M2[s2] = s1;
	}
	int q;
	cin >> q;
	for ( int i = 1 ; i <= q ; ++i ){
		int type;
		cin >> type;
		
		if ( type == 1 ){
			int x; cin >> x;
			if ( !G[x].empty() ){
				G[x].clear(); front[x] = 0;
			}
		}
		if ( type == 2 ){
			int x; string s; cin >> x >> s;
			G[x].push_back(s);
		}
		if ( type == 3 ){
			int x; cin >> x;
			++front[x];
		}
		if ( type == 4 ){
			int x; cin >> x;
			
			int gasit = 0;
			for ( int i = (int)G[x].size()-1 ; i >= front[x] ; --i ){
				string s1,s2;
				s1 = G[x][i];
				if ( M1[s1] != "" ){
					s2 = M1[s1];
				}
				else{
					s2 = M2[s1];
					swap(s1,s2);
				}
				if ( i != (int)G[x].size()-1 ){
					cout << " ";
				}
				cout << s1 << " " << s2;
				gasit = 1;
			}
			if ( !gasit )	cout << -1;
			cout << "\n";
		}
		if ( type == 5 ){
			string s; cin >> s;
			
			int found = -1;
			for ( int x = 1 ; x <= n && found == -1 ; ++x ){
				for ( int i = front[x] ; i < (int)G[x].size() && found == -1 ; ++i ){
					string &snow = G[x][i];
					if ( snow == s || M1[snow] == s || M2[snow] == s ){
						found = x;
					}
				}
			}
			
			cout << found << "\n";
		}
	}
	
	return 0;
}