#include <iostream>
#include <cstring>

using namespace std;

char nume[1000][1000], prenume[1000][1000], p[1000];
int n, m, i, t, com, que, stare[1000], lcecod[1000], CNTR[1000][1000], nrom[1000], k, j;

struct cozi {
    int in, sf;
};

cozi v[1000];

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

    for(i = 1;i <= m;i++) {
        cin >> nume[i] >> prenume[i];
    }

    cin >> t;

    for(i = 1;i <= t;i++) {
        v[i].in = 1;
    }

    for(i = 1;i <= t;i++) {
        cin >> com;

        if(com == 1) {
            cin >> que;

            stare[que] = (stare[que] + 1) % 2;

            if(stare[que] == 0) {
                for(j = 1;j <= m;j++) {
                    if(que == lcecod[j]) lcecod[j] = 0;
                }

                v[que].in = ++v[que].sf;
                nrom[que] = 0;
            }

        }

        if(com == 2) {
            cin >> que >> p;

            k = 0;
            for(j = 1;j <= m;j++) {
                if((strcmp(nume[j], p) == 0) || (strcmp(prenume[j], p) == 0)) {
                    k = 1;
                    break;
                }
            }
            lcecod[j] = que;
            CNTR[que][++v[que].sf] = j;
            nrom[que]++;
        }

        if(com == 3) {
            cin >> que;

            lcecod[CNTR[que][v[que].in]] = 0;

            v[que].in++;
            nrom[que]--;
        }

        if(com == 4) {
            cin >> que;

            if(nrom[que] == 0) cout << "-1\n";
            else {
                for(j = v[que].sf;j >= v[que].in;j--) {
                    cout << nume[CNTR[que][j]] << ' ' << prenume[CNTR[que][j]] << ' ';
                }

                cout << '\n';
            }
        }

        if(com == 5) {
            cin >> p;

            k = 0;
            for(j = 1;j <= m;j++) {
                if((strcmp(nume[j], p) == 0) || (strcmp(prenume[j], p) == 0)) {
                    k = 1;
                    break;
                }
            }

            if(k == 1) {
                if(lcecod[j] == 0) cout << "-1\n";
                else cout << lcecod[j] << '\n';
            }
        }
    }

    return 0;
}