#include <bits/stdc++.h>
  
 
  
using namespace std;
  
 
  
ifstream fin("nfa.in");
  
ofstream fout("nfa.out");
  
 
  
class NFA {
  
private:
  
  static const int SIGMA = 26;
  
  int no_states, no_trans, no_final_states, initial_state;
  
  unordered_set <int> final_states;
  
  struct node {
  
    vector <int> T[SIGMA];
  
  };
  
  vector <node> G;
  
 
  
  static inline bool cmp(const string &lsh, const string &rsh) {
  
    if (lsh.size() == rsh.size())
  
      return lsh < rsh;
  
    return lsh.size() < rsh.size();
  
  }
  
 
  
public:
  
  void add_edge(const int &node1, const int &node2, const char &ch) {
  
    G[node1].T[ch - 'a'].push_back(node2);
  
  }
  
 
  
  friend istream& operator >> (istream &in, NFA &obj) {
  
    in >> obj.no_states >> obj.no_trans >> obj.no_final_states >> obj.initial_state;
  
    --obj.initial_state;
  
    for (int idx = 0; idx < obj.no_final_states; ++idx) {
  
      int x; in >> x;
  
      --x;
  
      obj.final_states.emplace(x);
  
    }
  
    obj.G.resize(obj.no_states);
  
 
  
    for (int idx = 0; idx < obj.no_trans; ++idx) {
  
      int x, y; char ch;
  
      in >> x >> y >> ch;
  
      --x; --y;
  
      obj.add_edge(x, y, ch);
  
    }
  
 
  
    //in >> obj.initial_state >> obj.no_final_states;
  
 
  
    return in;
  
  }
  
 
  
  bool check(const string &s) {
  
    queue < pair <int, int> > q;
  
    vector < vector <bool> > vis;
  
    vis.resize(no_states + 5);
  
    for (auto& it : vis) {
  
      it.resize(s.size() + 5, false);
  
    }
  
    //set < pair <int, int> > in_queue;
  
    q.push({initial_state, 0});
  
    //in_queue.emplace(make_pair(initial_state, 0));
  
    vis[initial_state][0] = true;
  
 
  
    while (!q.empty()) {
  
      int node = q.front().first;
  
      int letter = q.front().second;
  
      q.pop();
  
      //in_queue.erase(make_pair(node, letter));
  
 
  
      vis[node][letter] = false;
  
 
  
      if (letter == (int)s.size()) {
  
        if (final_states.find(node) != final_states.end()) return true;
  
        continue;
  
      }
  
 
  
      for (auto &it : G[node].T[s[letter] - 'a'])
  
        //if (in_queue.find(make_pair(it, letter + 1)) == in_queue.end()) {
  
          //in_queue.emplace(make_pair(it, letter + 1));
  
        if (!vis[it][letter + 1]) {
  
          vis[it][letter + 1] = true;
  
          q.push({it, letter + 1});
  
        }
  
        //}
  
    }
  
    return false;
  
  }
  
 
  
  void get_words() {
  
    queue < pair <int, string> > q;
  
    set < pair <int, string> > in_queue;
  
    q.push({initial_state, ""});
  
    in_queue.emplace(make_pair(initial_state, ""));
  
    unordered_set <string> words;
  
 
  
    while (!q.empty() and words.size() < 100) {
  
      int node = q.front().first;
  
      string word = q.front().second;
  
      q.pop();
  
      in_queue.erase(make_pair(node, word));
  
 
  
      if (final_states.find(node) != final_states.end())
  
        words.emplace(word);
  
      if (words.size() >= 100) break;
  
 
  
      for (int i = 0; i < SIGMA; ++i)
  
        for (auto& it : G[node].T[i]) {
  
          word.push_back(char(i + 'a'));
  
          if (in_queue.find(make_pair(it, word)) == in_queue.end()) {
  
            in_queue.emplace(make_pair(it, word));
  
            q.push({it, word});
  
          }
  
          word.pop_back();
  
        }
  
    }
  
 
  
    vector <string> ans;
  
    for (auto& it : words)
  
      ans.emplace_back(it);
  
    sort(ans.begin(), ans.end(), cmp);
  
 
  
    fout << "Cele mai mici " << ans.size() << " de cuvinte acceptate sunt:\n"; // ans.size() < 100 => automtul nu accepta 100 de cuvinte
  
    for (auto &it : ans)
  
      fout << it << '\n';
  
  }
  
};
  
 
  
int main() {
  
  NFA A;
  
  fin >> A;
  
  int Q; fin >> Q;
  
  string s;
  
  while (Q--) {
  
    fin >> s;
  
    fout << A.check(s) << '\n';
  
  }
  
  //A.get_words();
  
 
  
  return 0;
  
}