#include <iostream>
#include <utility>
#include <string>
#include <vector>
#include <map>
#include <deque>
using namespace std;

int main(){
    int n,m; cin>>n>>m;

    vector< pair<string,string> > names(m);
    map<string,int> which_person;
    
    for(int i=0;i<m;++i){
        cin >> names[i].first >> names[i].second;
        which_person[names[i].first] = i;
        which_person[names[i].second] = i;
    }

    vector< deque<int> > queues(n+1);
    vector<int> where(m,-1);

    int t; cin>>t;
    while(t--){
        int opt,x,id;
        string name;
        cin>>opt;
 
       switch(opt){
            case 1:
                cin>>x;
                for(auto it=queues[x].begin(); it!=queues[x].end(); ++it)
                    where[*it]=-1;
                queues[x].clear();
                break;

            case 2:
                cin>>x;
                cin>>name;
                id=which_person[name];
                queues[x].push_back(id);
                where[id]=x;
                break;

            case 3:
                cin>>x;
                where[queues[x].front()]=-1;
                queues[x].pop_front();
                break;

            case 4:
                cin>>x;
                if(queues[x].empty()) cout<<-1;
                for(auto rit=queues[x].rbegin(); rit!=queues[x].rend(); ++rit)
                    cout<<names[*rit].first<<' '<<names[*rit].second<<' ';
                cout<<'\n';
                break;

            case 5:
                cin>>name;
                cout<<where[which_person[name]]<<'\n';
                break;

            default: return 1;
        }
    }
}