#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef struct {string na, sur;int ind;}PASAG;
PASAG pas[101];
vector <int> co[101];
bool des[101];
int m;
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;
	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)
				{
					cout<<"-1\n";
				}
				else
				{
					for(i=0;i<co[x].size();i++)
						cout<<pas[co[x][i]].na<<" "<<pas[co[x][i]].sur+" ";
					cout<<'\n';
				}
				break;
			}
			case 5:
			{
				cin>>myn;
				poz=cauta(myn);
				cout<<pas[poz].ind<<'\n';
			}
		}
	}
	return 0;
}