#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>

using namespace std;

const char infile[] = "input.in";
const char outfile[] = "output.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 105;
const int oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

queue <int> Q[MAXN];
map<string, int> mp;
map<int, pair<string, string> > mpi;
int N, M, T, where[MAXN];
bitset <MAXN> Used;

void write(queue <int> &q) {
    if(q.empty())
        return;
    int x = q.front();
    q.pop();
    write(q);
    cout << mpi[x].first << ' ' << mpi[x].second << ' ';
}

int main() {
    cin.sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    #endif
    cin >> N >> M;
    for(int i = 1 ; i <= M ; ++ i) {
        string a, b;
        cin >> a >> b;
        mp[a] = i;
        mp[b] = i;
        mpi[i] = make_pair(a, b);
    }
    cin >> T;
    /*1 x
    Counter x changes its state (open/closed). If x closes then all the people waiting there leave.
    2 x myName
    A person with the name or surname myName queues at ticket counter x.
    3 x
    The first person waiting in line at counter x is served and then leaves the queue.
    4 x
    Comisia wants you to output on a line the full names (name + surname) of all the people waiting in line at counter x, from last to first. If there are no people waiting at counter x, output -1.
    5 myName
    Output the index of the queue where person myName is waiting. If the person is not part of a queue, output -1.*/
    for(int q = 1 ; q <= T ; ++ q) {
        int op, x;
        string a;
        cin >> op;
        if(op == 5) {
            cin >> a;
            if(where[mp[a]])
                cout << where[mp[a]] << '\n';
            else cout << "-1\n";
            continue;
        }
        switch(op) {
        case 1:
            cin >> x;
            Used[x] = (! Used[x]);
            if(Used[x])
                while(!Q[x].empty()) {
                    where[Q[x].front()] = 0;
                    Q[x].pop();
                }
            break;
        case 2:
            cin >> x >> a;
            Q[x].push(mp[a]);
            where[mp[a]] = x;
            break;
        case 3:
            cin >> x;
            where[Q[x].front()] = 0;
            Q[x].pop();
            break;
        case 4:
            cin >> x;
            queue <int> actQ = Q[x];
            if(Q[x].empty())
                cout << "-1";
            else
                write(Q[x]);
            Q[x] = actQ;
            cout << '\n';
            break;
        }
    }
    fin.close();
    fout.close();
    return 0;
}