#include <iostream>
#include <deque>
#include <string>
using namespace std;

struct oseba{
	string ime, priimek;
	int vrsta;
}oseba[101];

deque<int> vrsta[101];
bool counter[101];
int main(){
	deque<int>::reverse_iterator it;
	int N, M, T;
	int mode, k;
	string s;
	cin>>N>>M;
	for(int i=0; i<101; i++)	counter[i] = false;
	for(int i=0; i<M; i++){
		cin>>oseba[i].ime>>oseba[i].priimek;
		oseba[i].vrsta = -1;
	}
	cin>>T;
	for(int i=0; i<T; i++){
		cin>>mode;
		if(mode == 1){
			cin>>k;
			counter[k] = !counter[k];
			if(counter[k] == false){
				it = vrsta[k].rbegin();
				while(it != vrsta[k].rend()){
					mode = *it;
					oseba[mode].vrsta = -1;
					it++;
				}
				vrsta[k].clear();
			}
		}
		else if(mode == 2){
			cin>>mode>>s;
			for(int x=0; x<M; x++){
				if(oseba[x].ime.compare(s) == 0 || oseba[x].priimek.compare(s) == 0){
					k = x;
					break;
				}
			}
			vrsta[mode].push_back(k);
			oseba[k].vrsta = mode;
		}
		else if(mode == 3){
			cin>>k;
			mode = *(vrsta[k].begin());
			oseba[mode].vrsta = -1;
			vrsta[k].pop_front();
		}
		else if(mode == 4){
			cin>>k;
			if(vrsta[k].empty()){
				cout<<-1<<'\n';
			}
			else{
				it = vrsta[k].rbegin();
				while(it != vrsta[k].rend()){
					cout<<oseba[*it].ime<<' '<<oseba[*it].priimek<<' ';
					it++;
				}
				cout<<'\n';
			}
		}
		else{//mode == 5
			cin>>s;
			for(int y = 0; y<M; y++){
				if(oseba[y].ime.compare(s)==0 || oseba[y].priimek.compare(s)==0){
					k=y;
				}
			}
			cout<<oseba[k].vrsta<<'\n';
		}
	}
	return 0;
}