#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef struct {string na, sur;int ind;}PASAG;
typedef struct {bool tip;string str;int nr;}RASP;
PASAG pas[101];
vector <int> co[101];
bool des[101];
int m;
vector <RASP> rez;
int cauta(string myn)
{
	int i;
	for(i=1;i<=m;i++)
		if((myn==pas[i].na)||(myn==pas[i].sur))
			return i;
	return 0;
}
int main()
{
	int n,t;
	int i,ii;
	int caz,x;
	string myn;
	int poz;
	RASP rs;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>pas[i].na>>pas[i].sur;
		pas[i].ind=-1;
	}
	cin>>t;
	for(ii=1;ii<=t;ii++)
	{
		cin>>caz;
		switch(caz)
		{
			case 1:
			{
				cin>>x;
				if(des[x])
				{
					des[x]=0;
					for(i=0;i<co[x].size();i++)
						pas[co[x][i]].ind=-1;
					co[x].erase(co[x].begin(), co[x].end());
				}
				else
					des[x]=1;
				break;
			}
			case 2:
			{
				cin>>x>>myn;
				poz=cauta(myn);
				co[x].insert(co[x].begin(),poz);
				pas[poz].ind=x;
				break;
			}
			case 3:
			{
				cin>>x;
				pas[co[x][co[x].size()-1]].ind=-1;
				co[x].pop_back();
				break;
			}
			case 4:
			{
				cin>>x;
				if(co[x].size()==0)
				{
					rs.tip=0;
					rs.str="-1";
				}
				else
				{
					rs.tip=0;
					rs.str="";
					for(i=0;i<co[x].size();i++)
						rs.str=rs.str+pas[co[x][i]].na+" "+pas[co[x][i]].sur+" ";
				}
				rez.push_back(rs);
				break;
			}
			case 5:
			{
				cin>>myn;
				poz=cauta(myn);
				rs.tip=1;
				rs.nr=pas[poz].ind;
				rez.push_back(rs);
			}
		}
	}
	for(i=0;i<rez.size();i++)
	{
		if(!rez[i].tip)
		{
			cout<<rez[i].str<<'\n';
		}
		else
			cout<<rez[i].nr<<'\n';
	}
	return 0;
}