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

ifstream in("nfa.in");
ofstream out("nfa.out");
class Automata
{
private:
    int nrStates, nrTransitions, nrFinalStates, initialState;
    set <int> finalState;
    multimap < pair <int, int>, char> transitions;
    int nrWords;
    string word;
    set <pair <int, int> > visited;

public:
    Automata()
    {   // read the number of states
        in >> nrStates;
        ///cout << "Number of states: " << nrStates << '\n';
        // read the number of transitions
        in >> nrTransitions;
        ///cout << "Number of transitions: " << nrTransitions << '\n';
        // read the number of final states
         in >> nrFinalStates;
        ///cout << "Number of final states: " << nrFinalStates << '\n';
        // read the initial state
        in >> initialState;
        ///cout << "Initial state: " << initialState << '\n';
        // read the number of the final states and the states
        int f;
        for(int i = 0; i < nrFinalStates; ++i)
        {
            in >> f;
            finalState.insert(f-1);
        }
        // read the transitions
        int source, destination;
        char letter;
        for(int i = 0; i < nrTransitions; ++i)
        {
            in >> source >> destination >> letter;
            pair <int, int> p;
            p.first = source-1;
            p.second = destination-1;
            transitions.insert(pair <pair <int, int>, char> (p, letter));
        }
        multimap < pair <int, int>, char> ::iterator itr;
        for(itr = transitions.begin(); itr != transitions.end(); ++itr)
            ///cout << itr -> first.first << " " << itr -> first.second << " "<< itr -> second << '\n';

        set <int> ::iterator itr2;
        ///for(itr2 = finalState.begin(); itr2 != finalState.end(); ++itr2)
            ///cout << *itr2 << " ";
        ///cout << '\n';
        //trebuie sa schimb ca sa iau fiecare word pe rand
        // mai bine fac un get pentru fiecare word
        // hai ca am schimbat pana la urma
        in >> nrWords;
        ///cout << "Number of words: " << nrWords << '\n';
    }
    bool acceptedNFA(string word, int currentState, unsigned int i);
    void showResultsNFA();
};

bool Automata::acceptedNFA(string word, int currentState, unsigned int i){
    visited.insert(make_pair(currentState, i));
    if(i == word.size())
        {if(finalState.find(currentState) != finalState.end())
            return true;
        else
            return false;
        }
    bool accepted = false;
    for(int j = 0; j < nrStates; ++j)
        if(transitions.find(make_pair(currentState, j))->second == word[i])
                accepted =  accepted || acceptedNFA(word, j, i+1);

    return accepted;
}
void Automata::showResultsNFA(){
    visited.clear();
    for(int i = 0; i < nrWords; ++i)
        {in >> word;
        out << acceptedNFA(word, initialState, 0) << '\n';
        }
}
int main()
{
    Automata A;
    A.showResultsNFA();
    ///cout <<"\n";
    ///cout << "Hello world!" << endl;
    return 0;
}