//Codeforces 233
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#include <deque>
#include <unordered_map>

using namespace std;

const int INF = 1 << 30;
const int MAX_N = 105;

int N, M, T;
pair<string, string> full_name[MAX_N];
unordered_map<string, int> names_map;
deque<int> qs[MAX_N];
bool open[MAX_N];

int in_q[MAX_N];

int main() {
  cin >> N >> M;

  for (int i = 1; i <= M; i += 1) {
    cin >> full_name[i].first >> full_name[i].second;
    names_map[full_name[i].first] = names_map[full_name[i].second] = i;
  }

  for (int i = 1; i <= M; i += 1) in_q[i] = -1;

  cin >> T;
  for (int t = 1, op; t <= T; t += 1) {
    cin >> op;
    int counter, index;
    string nm;
    if (op == 1) {
      cin >> counter;

      if (open[counter]) {
        while (not qs[counter].empty()) {
          in_q[qs[counter].front()] = -1;
          qs[counter].pop_front();
        }
      }
      open[counter] ^= 1;
    } else if (op == 2) {
      cin >> counter >> nm;

      index = names_map[nm];
      qs[counter].push_front(index);
      in_q[index] = counter;
    } else if (op == 3) {
      cin >> counter;
      in_q[qs[counter].back()] = -1;
      qs[counter].pop_back();
    } else if (op == 4) {
      cin >> counter;
      if (qs[counter].empty()) {
        cout << -1 << '\n';
      } else {
        for (auto x: qs[counter]) {
          cout << full_name[x].first << ' ' << full_name[x].second << ' ';
        }
        cout << '\n';
      }
    } else {
      cin >> nm;
      index = names_map[nm];
      cout << in_q[index] << '\n';
    }
  }
  return 0;
}