// 行列の累乗 + 構文解析

// ライブラリ
#include<vector>
#include<cassert>
// 定数
const int ZERO = 0; // 零元
const int UNIT = 1; // 単位元
// 構造体
template<typename T>
struct Matrix {
  std::vector<std::vector<T>> element;
  int rows, columns;
  // 零行列で初期化
  Matrix() {}
  explicit Matrix(int n) : rows(n), columns(n), element(n, std::vector<T>(n, ZERO)) {}
  Matrix(int r, int c) : rows(r), columns(c), element(r, std::vector<T>(c, ZERO)) {}
};
// 演算
Matrix<int> add(const Matrix<int>& lhs, const Matrix<int>& rhs);
Matrix<int> multiply(const Matrix<int>& lhs, const Matrix<int>& rhs);
// 単位行列 O(n)
template<typename T>
Matrix<T> identity(int n) {
  Matrix<T> result(n);
  for(int i = 0; i < n; ++i) result.element[i][i] = UNIT;
  return result;
}
// 乗算 O(n^3)
template<typename T>
Matrix<T> operator*(const Matrix<T>& lhs, const Matrix<T>& rhs) {
  assert(lhs.columns == rhs.rows);
  Matrix<T> result(lhs.rows, rhs.columns);
  for(int i = 0; i < lhs.rows; ++i)
    for(int j = 0; j < rhs.columns; ++j)
      for(int k = 0; k < lhs.columns; ++k)
        result.element[i][j] += lhs.element[i][k] * rhs.element[k][j];
  return result;
}
// 累乗 O(n^3 * log(n))
template<typename T>
Matrix<T> power(const Matrix<T>& m, int n) {
  assert(m.rows == m.columns);
  if(!n) return identity<T>(m.rows);
  if(n & 1) return multiply(m, power(m, n - 1));
//   if(n & 1) return power(m * m, n >> 1) * m;  // こっちだと再帰呼び出しが減る代わりに無駄な乗算が1回増える
  return power(multiply(m, m), n >> 1);
}

// デバッグ用
#include<iostream>
template<typename T> std::ostream& operator<<(std::ostream& os, const Matrix<T>& m) {
  for(const auto& r: m.element) {
    for(const auto& e: r) os << " " << e;
    os << std::endl;
  }
  return os;
}
////////////////////////////////////////////////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

// 演算
Matrix<int> add(const Matrix<int>& lhs, const Matrix<int>& rhs) {
  const int N = lhs.rows;
  Matrix<int> result(N);
  for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j)
    if(rhs.element.at(i).at(j)) result.element[i] = lhs.element.at(j);
  return result;
}
Matrix<int> multiply(const Matrix<int>& lhs, const Matrix<int>& rhs) {
  return add(lhs, rhs);
}

// 構文解析
Matrix<int> parse(const string& expression, int& i, const unordered_map<char, Matrix<int>>& part);
Matrix<int> term(const string& expression, int& i, const unordered_map<char, Matrix<int>>& part);
int number(const string& expression, int& i);

Matrix<int> parse(const string& expression, int& i, const unordered_map<char, Matrix<int>>& part) {
  Matrix<int> result = term(expression, i, part);
  while(expression[i] == '+') {
    ++i;
    result = add(result, term(expression, i, part));
  }
  return result;
}
Matrix<int> term(const string& expression, int& i, const unordered_map<char, Matrix<int>>& part) {
  Matrix<int> result;
  if(expression[i] == '(') {
    ++i;
    result = parse(expression, i, part);
    ++i;
  } else if(isdigit(expression[i])) {
    int left = number(expression, i);
    auto right = term(expression, i, part);
    result = power(right, left);
  } else {
    result = part.at(expression[i]);
    ++i;
  }
  return result;
}
int number(const string& expression, int& i) {
  int result = 0;
  while(isdigit(expression[i])) {
    result *= 10;
    result += expression[i] - '0';
    ++i;
  }
  return result;
}

// メイン
int main() {
  int N, K;
  cin >> N >> K;

  unordered_map<char, Matrix<int>> part;
  for(int k = 0; k < K; ++k) {
    char p; int h;
    cin >> p >> h;
    auto m = identity<int>(N);
    for(int i = 0; i < h - 1; ++i) for(int j = 0; j < N - 1; ++j) {
      int g;
      cin >> g;
      if(g) swap(m.element[j], m.element[j + 1]);
    }
    part[p] = m;
  }

  int E;
  cin >> E;
  for(int e = 0; e < E; ++e) {
    string expression;
    cin >> expression;
    int t = 0;
    auto answer = parse(expression, t, part);
    for(int i = 0; i < N; ++i) {
      if(i) cout << " ";
      for(int j = 0; j < N; ++j) if(answer.element[i][j]) cout << j + 1;
    }
    cout << endl;
  }
}

Measured memory_bytes: 1336