#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <algorithm>

class Automaton
{
    int start_state;
    std::unordered_set<int> final_states;
    std::vector<std::unordered_map<char, std::vector<int>>> transitions;
public:
    Automaton();
    Automaton(int);
    friend std::istream& operator >> (std::istream&, Automaton&);
    bool isAccepted(const std::string);
};

Automaton::Automaton() {}

Automaton::Automaton(int nr_states):
    transitions(std::vector<std::unordered_map<char, std::vector<int>>>(nr_states + 1)) {}

std::istream& operator >> (std::istream& in, Automaton& automaton) {
    int n, m;
    in >> n;    // n = number of states
    in >> m;    // m = number of transition functions

    automaton = Automaton(n);

    int t;
    in >> t; // cardinal of the final state set

    in >> automaton.start_state; // start state

    for (int i = 0; i < t; ++i){
        int q;
        in >> q;
        automaton.final_states.insert(q);   // store the final state set in unordered_set
    }

    for (int i = 0; i < m; ++i){
        int q1, q2; // states corresponding to a transition function
        char ch;    // character of the input alphabet
        in >> q1 >> q2 >> ch;
        automaton.transitions[q1][ch].emplace_back(q2);
    }

    return in;
}

bool Automaton::isAccepted(std::string word) {
    std::vector<bool> inQueue(transitions.size() + 1, 0);
    std::vector<int> q;
    q.emplace_back(start_state);

    for(int i = 0; i < (int)word.size(); i++) {
        char letter = word[i];
        std::vector<int> temp;   // next states

        for (auto& node : q) {
            for (auto& son : transitions[node][letter]) {
                if (inQueue[son] == 0) {
                    temp.emplace_back(son);
                    inQueue[son] = 1;
                }
            }
        }
        for(auto &nod : q)
            inQueue[nod] = 0;

        q = temp;
    }

    for(auto& node : q)
        if (final_states.find(node) != final_states.end())
            return true;
    return false;
}

int main()
{
    std::ifstream InputFile;
    InputFile.open("nfa.in");

    std::ofstream OutputFile;
    OutputFile.open("nfa.out");

    Automaton automaton;
    InputFile >> automaton;

    int nr_queries;
    InputFile >> nr_queries;

    for (int i = 0; i < nr_queries; i++){
        std::string s;
        InputFile >> s;
        OutputFile << automaton.isAccepted(s) << '\n';
    }

    InputFile.close();
    OutputFile.close();
    return 0;
}