#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    int n, m, nr;
    int op, opnr;
    cin >> n >> m;
    int cnt[n+1];
    int first[n+1];
    for(int i = i; i <= n; i++) {
        cnt[i] = 0;
        first[i] = -1;
    }
    char name    [m][20];
    char surname [m][20];
    char str[20];
    int  qnr     [m];
    int  next    [m];
    int  prev    [m];
    for(int i = 0; i < m; i++) {
        qnr[i]  = -1;
        next[i] = -1;
        prev[i] = -1;
    }
    for(int i = 0; i < m; i++) {
        cin >> name[i] >> surname[i];
    }
    cin >> opnr;
    for(int opi = 0; opi < opnr; opi++) {
        cin >> op;
        switch(op) {
        case 1: {
            cin >> nr;
            if(cnt[nr] == 0) {
                cnt[nr] = 1;
                first[nr] = -1;
            }
            else {
                int current;
                int following = first[nr];
                if(following != -1) {
                    while(following != -1) {
                        current = following;
                        following = next[current];
                    }
                    int previous = prev[current];
                    while(previous != -1) {
                        qnr[current]  = -1;
                        next[current] = -1;
                        prev[current] = -1;
                        current = previous;
                        previous = prev[current];
                    }
                    qnr[current] = -1;
                    next[current] = -1;
                }
                cnt[nr] = 0;
                first[nr] = -1;
            }
            break;
        }
        case 2: {
            cin >> nr;
            cin >> str;
            for(int i = 0; i < m; i++) {
                if(strcmp(str,name[i]) == 0 || strcmp(str,surname[i]) == 0) {
                    qnr[i] = nr;
                    if(first[nr] == -1)
                        first[nr] = i;
                    else {
                        int current = first[nr];
                        int following = next[current];
                        while(following != -1) {
                            current = following;
                            following = next[current];
                        }
                        next[current] = i;
                        prev[i] = current;
                    }
                    break;
                }
            }
            break;
        }
        case 3: {
            cin >> nr;
            int served = first[nr];
            int following = next[served];
            if(following != -1) {
                first[nr] = following;
                prev[following] = -1;
            }
            else {
                first[nr] = -1;
            }
            next[served] = -1;
            qnr[served]  = -1;
            break;
        }
        case 4: {
            cin  >> nr;
            if(first[nr] == -1) {
                cout << -1 << endl;
                break;
            }
            int current = first[nr];
            int following = next[current];
            while(following != -1) {
                current = following;
                following = next[current];
            }
            int previous = prev[current];
            while (previous != -1) {
                cout << name[current] << surname [current];
                current = prev[current];
                previous = prev[current];
            }
            cout << name[current] << surname [current] << endl;
            break;
        }
        case 5: {
            cin >> str;
            for(int i = 0; i < m; i++) {
                if(strcmp(str,name[i]) == 0 || strcmp(str,surname[i]) == 0) {
                    cout << qnr[i] << endl;
                    break;
                }
            }
            break;
        }
        }
    }
}