#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>

class FA
{ /// abstract implementation of a finite automata
protected:
    int startState;
    std::unordered_set<int> finalStates; /// unordered_set for O(1) verification if a state is final.
    std::unordered_map<int, std::unordered_map<char,std::unordered_set<int> > > edges;
    /// edges is an adjacency list. [StartingNode] [Edge "cost"/letter] [EndingNode].
    /// Why so many unordered? For theoretical O(1) access. When using the list I go on transitions based on the
    /// letter more than based on the next node, so it comes before for faster access.
    /// The set is used for lambdaNFAs to search for the lambda transition. It also is compatible with DFA/NFA.

    virtual void path(std::string word) = 0;/// displays path in console. (on DFA) should be used
    void runTests(std::istream& in,std::ostream& out, bool outputPath = true)
    { /// without the implementation of accepted() and path() it doesn't work.
    /// Therefore, it only becomes public in derived classes.
        int testCount;
        in >> testCount;
        for(int i=0;i<testCount;i++)
        {
            std::string word;
            in >> word;
            if(word == "_") word = ""; /// Empty word is considered to be the underscore.
            if(accepted(word))
            {
                out << "1\n"; /// means Yes (the word is accepted)
                if(outputPath)
                {std::cout << "Drumul este: "; /// means "The path is: "
                path(word);
                std::cout << '\n';

                }

            }
            else
            {
                out << "0\n"; /// means No
                if(outputPath)
                    std::cout << "Cuvantul nu e acceptat.\n"; /// means "The word isn't accepted."
            }
        }
    }
public:
    FA(){}
    FA(const FA& fa):startState(fa.startState),edges(fa.edges){}
    void read(std::istream& in)
    {/// input data format is present in requirements.txt

        int n,m;
        std::deque<int> states;
        int nrFinalStates;
        /// Didn't use these variables so I didn't put them as members.

        in >> n >> m >> nrFinalStates;

        in >>startState;

        for(int i=0;i<nrFinalStates;i++)
        {
            int state;
            in >> state;
            finalStates.insert(state);
        }

        for(int i=0;i<m;i++)
        {
            int startNode, endNode;
            char letter;
            in >> startNode >> endNode >> letter;
            edges[startNode][letter].insert(endNode);
        }

    }
    virtual bool accepted(std::string word, bool a = false) = 0; /// implemented in non-abstract FA.
    friend std::istream& operator>>(std::istream& in, FA& myDFA);
};
std::istream& operator>>(std::istream& in, FA& myFA)
{
    myFA.read(in);
    return in;
}
class NFA : public FA
{
public:
    using FA::runTests;
    void path(std::string word){
        accepted(word,true);
    }
    void printPath(std::deque<int> nodes, int lastNode)
    {
        while(!nodes.empty())
        {
            std:: cout << nodes.front() << ' ';
            nodes.pop_front();
        }
        std::cout << lastNode;
    }


    /// Slightly OVERCOMPLICATED (took some time to debug). works but not traditional DFS.
    /// It was the first solution to also output the path that I thought of.
    /// Uses a stack of iterators, which ended up needing the last node
    /// to verify that the end of the iterator isn't reached (luckily
    /// prevNodes is also used in outputing the result).

    /// It doesn't use a normal stack because I thought it would be too memory
    /// inefficient to have worst case of n states per every l letter stored instead of l iterators.
    /// At lambda-NFA I gave up on this design in favor of simplicity.
    bool accepted(std::string word,bool outputPath = false)
    {
        return acceptedDFS(word,startState);
        if(word.size() == 0) /// empty word (lambda)
            return (finalStates.find(startState) != finalStates.end());
        if(edges[startState].find(word[0]) == edges[startState].end())
            return false; /// if the first letter doesn't lead anywhere

        std::deque<int> prevNodes;
        prevNodes.push_back(startState);

        std::stack< std::unordered_set<int>::iterator > its;
        its.push(edges[startState][word[0]].begin());

        /// this for loop is just weird. i is the index of the place in the word
        /// and when going on a bad path we decrease it once (i-=2;i++). So it
        /// has to end when running out of every path (backtracking to 0th letter).
        for(int i=1;i >= 0; i++)
        {
            if(its.empty())return false;
            if(its.top() == edges[prevNodes.back()][word[i-1]].end())
            {/// if we reached the end of the current iterator.
                i-=2;
                its.pop();
                prevNodes.pop_back();
                if(!its.empty())
                    its.top()++;
                continue;
            }
            int node = *(its.top());

            if((unsigned)i == word.size())
            { /// reached the end of the word; testing if finalState.
                if (finalStates.find(node) != finalStates.end())
                {
                    if(outputPath)
                        printPath(prevNodes,node);
                    return true;
                }
                i-=1;
                its.top()++;
                continue;
            }


            if(edges[node].find(word[i]) == edges[node].end())
            {/// testing if transition doesn't exists
                i-=1;
                its.top()++;
                continue;
            }
            prevNodes.push_back(node);
            its.push(edges[node][word[i]].begin());
        }
        return false;
    }

    /// classic recursive DFS. Didn't know how to show path so I codded the overcomplicated one.
    bool acceptedDFS(std::string word, int node,int i=0)
    {
        if((unsigned)i == word.size())
            return (finalStates.find(node) != finalStates.end());

        if(edges[node].find(word[i]) != edges[node].end())
            for(const auto& nextNode:edges[node][word[i]])
                if(acceptedDFS(word,nextNode,i+1))
                    return true;
        return false;
    }

    /// first coded. Doesn't output path (can't remember where all paths came from).
    bool acceptedBFS(std::string word)
    {
        if(word.size() == 0)
            return (finalStates.find(startState) != finalStates.end());
        std::unordered_set<int> nodes;
        nodes.insert(startState);
        for(unsigned int i = 0; i < word.size(); i++)
        {
            std::unordered_set<int> oldNodes = nodes;
            nodes.clear();
            for(const auto& node:oldNodes)
            {
                if(edges[node].find(word[i]) != edges[node].end())
                    for(const auto& nextNode:edges[node][word[i]])
                        nodes.insert(nextNode);
            }
            if(nodes.empty()) return false;
        }
        for (const auto& node: nodes)
            if(finalStates.find(node) != finalStates.end())
                return true;
        return false;
    }
};

int main()
{
#ifdef fakeFILES
std::ifstream fin("input.in");
std::ofstream fout("input.out");
#else
std::ifstream fin("nfa.in");
std::ofstream fout("nfa.out");
#endif
    NFA automata;
    fin >> automata;
    automata.runTests(fin,fout,false);
}