#include <iostream>
#include <string>
#include <list>
#include <cstdio>
#define DN 100
using namespace std;

int n,m,t,open[DN];
string fn[505],sn[505];
list<int> c[505];

int main() {
	//freopen("input.txt","r",stdin);
	cin>>n>>m;
	for(int i=0; i<m; ++i) cin>>fn[i]>>sn[i];
	cin>>t;
	for(;t--;) {
		int op,p; cin>>op;
		string name;
		if(op==1) {
			cin>>p;
			for(;c[p].size();c[p].pop_front());
			open[p]^=1;
		}else if(op==2) {
			cin>>p>>name;
			int ok=0;
			for(int i=0; i<m; ++i)
				if(fn[i]==name || sn[i]==name) {
					c[p].push_back(i);
					ok=1;
				}
		}else if(op==3) {
			cin>>p;
			c[p].pop_front();
		}else if(op==4) {
			cin>>p;
			if(c[p].size()) {
				list<int>::iterator it=c[p].end();
				--it;
				for(; it!=c[p].begin(); --it) cout<<fn[*it]<<' '<<sn[*it]<<"  ";
				cout<<fn[*c[p].begin()]<<' '<<sn[*c[p].begin()]<<'\n';
			}else cout<<"-1\n";
		}else {
			cin>>name;
			int ok=0;
			for(int i=1; i<=n; ++i)
				for(list<int>::iterator it=c[i].begin(); it!=c[i].end(); ++it)
					if(fn[*it]==name || sn[*it]==name) {
						ok=1;
						cout<<i<<'\n';
					}
			if(!ok) cout<<"-1\n";
		}
	}
}