#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <list>
using namespace std;

int n, m, t;
bool ok[105];
struct nume {
    char n1[25];
    char n2[25];
    int cntr;
} v_n[105];
vector< list<int> > cntrs(105);
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> v_n[i].n1;
        cin.getline(v_n[i].n2, 25);
        strcpy(v_n[i].n2, v_n[i].n2+1);
    }
    cin >> t;
    int op, x;
    for (int i = 0; i < t; ++i) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            ok[x] ? ok[x] = 0 : ok[x] = 1;
        }
        else if (op == 2) {
            cin >> x;
            char buf[25];
            cin.getline(buf, sizeof(buf));
            strcpy(buf, buf+1);
            int j = 0;
            while (strcmp(v_n[j].n1, buf) && strcmp(v_n[j].n2, buf)) ++j;
            cntrs[x].push_back(j);
            v_n[j].cntr = x;
        }
        else if (op == 3) {
            cin >> x;
            cntrs[x].pop_front();
        }
        else if (op == 4) {
            cin >> x;
            list<int>::iterator it = cntrs[x].end();
            --it;
            while (it != cntrs[x].begin()) {
                cout << v_n[*it].n1 << " " << v_n[*it].n2 << " ";
                --it;
            }
            cout << v_n[*it].n1 << " " << v_n[*it].n2 << " ";
            cout << "\n";
        }
        else if (op == 5){
            char buf[25];
            int j = 0;
            cin.getline(buf, sizeof(buf));
            strcpy(buf, buf+1);
            while (strcmp(v_n[j].n1, buf) && strcmp(v_n[j].n2, buf)) ++j;
            cout << v_n[j].cntr << "\n";
        }
    }
    return 0;
}