#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

struct PERSOANA{
    char nam[102],sur[102];
};

vector <PERSOANA> q[103];
char N[102][102], S[102][102];
int G,P;
bool stand[102];

void citire() {
    cin >> G >> P;
    for( int i=1; i<=P; i++ ) {
        cin >> N[i];
        cin >> S[i];
    }
}

void Operatie_1() {
    int st;
    cin >> st;
    if( stand[ st ] == 1 ) {
        q[ st ].clear();
        stand[ st ]= 0;
    }
    else stand[ st ]= 1;
}

void Operatie_2() {
    int st;
    cin >> st;
    char nume[102];
    cin >> nume;
    int poz= 0;
    for( int i=1; i<=P && poz==0; i++ ) {
        if( strcmp( nume , N[i] )==0 || strcmp( nume , S[i] )==0 ) poz= i;
    }
    PERSOANA aux;
    strcpy( aux.nam , N[ poz ] );
    strcpy( aux.sur , S[ poz ] );
    q[ st ].insert( q[st].begin(), aux );
}

void Operatie_3() {
    int st;
    cin >> st;
    q[ st ].pop_back();
}

void Operatie_4() {
    int st;
    cin >> st;
    for( int i=0; i<(int)q[st].size(); ++i ) {
        cout << q[st][i].nam << " " << q[st][i].sur << " ";
    }
    cout << '\n';
}

void Operatie_5() {
    char nume[103];
    cin >> nume;
    int R= 0;
    for( int i=1; i<=G && R==0; i++ ) {
        for( int j=0; j<(int)q[i].size() && R==0; j++ ) {
            if( strcmp( nume, q[i][j].nam )==0 || strcmp( nume , q[i][j].sur )==0 ) R= j+1;
        }
    }
    cout << R << '\n';
}

int main()
{
    citire();
    int nr_mutari;
    cin >> nr_mutari;
    for( int nrm=0; nrm<nr_mutari; nrm++ ) {
        int op;
        cin >> op;
        if( op == 1 ) Operatie_1();
        else if( op == 2 ) Operatie_2();
        else if( op == 3 ) Operatie_3();
        else if( op == 4 ) Operatie_4();
        else Operatie_5();
    }
    return 0;
}