#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <iostream>
using namespace std;

#define Nmax 128

string firstName[Nmax], lastName[Nmax], name;
int N, M, T, x, op;
list<int> queue[Nmax];
int where[Nmax];
char state[Nmax];
map<string, int> H;

int main() {
    freopen("test.in", "r", stdin);
    scanf("%d %d", &N, &M);
    for (int i=1; i<=M; ++i) {
        cin >> firstName[i] >> lastName[i];
        H[firstName[i]] = i;
        H[lastName[i]] = i;
    }
    
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &op);
        switch (op) {
            case 1:
                scanf("%d", &x);
                state[x] ^= 1;
                if (state[x] == 0) {
                    for (list<int>::iterator it = queue[x].begin(); it != queue[x].end(); ++it)
                        where[*it] = 0;
                    queue[x].clear();
                }
                break;
            case 2:
                cin >> x >> name;
                queue[x].push_back(H[name]);
                where[H[name]] = x;
                break;
            case 3:
                scanf("%d", &x);
                queue[x].pop_front();
                break;
            case 4:
                scanf("%d", &x);
                if (queue[x].size() == 0)
                    printf("-1\n");
                else {
                    for (list<int>::reverse_iterator it = queue[x].rbegin(); it != queue[x].rend(); ++it) {
                        if (it != queue[x].rbegin()) printf(" ");
                        printf("%s %s", firstName[*it].c_str(), lastName[*it].c_str());
                    }
                    printf("\n");
                }
                break;
            case 5:
                cin >> name;
                x = H[name];
                if (where[x]) printf("%d\n", where[x]);
                else printf("-1\n");
                break;
        }
    }
    
    return 0;
}