#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 l_NFA : public FA
{
protected:
    void path(std::string word)    {
        accepted(word,true);
    }

    /// helper function to get the lambda path between 2 nodes (used in printing path).
    std::deque<int> getLambdaPath(int prevNode, char c, int nextNode)
    {
        std::unordered_map<int,int> lambdaPath; /// has 2 uses: remembers what
        /// nodes have been visited (to ignore lambda cycles) and remembers from
        /// which node we got to the current node.
        lambdaPath[prevNode] = prevNode; /// to figure out it's the first one.

        std::stack<int> stk;
        stk.push(prevNode);
        while(!stk.empty())
        {
            int node = stk.top();
            if(edges[node][c].find(nextNode) != edges[node][c].end())
                break; /// if we found an edge to the desired next node we don't need to check any more nodes.
            stk.pop();

            for (const auto& sameNode:edges[node]['0'])
            { /// sameNode because we can get there through lambda transitions in the same step.
                if(lambdaPath.find(sameNode) != lambdaPath.end())
                    continue; /// if already visited we ignore it.
                stk.push(sameNode); /// we'll have to check it.
                lambdaPath[sameNode] =  node;
            }
        }
        if(stk.empty() || edges[stk.top()][c].find(nextNode) == edges[stk.top()][c].end())
            return {}; /// control case where no path was found or it doesn't lead correctly.

        /// backtracks to the beginning node, saving the nodes.
        int node = stk.top();
        std::deque<int> result;
        while(node != lambdaPath[node])
        {
            result.push_back(node);
            node = lambdaPath[node];
        }
        result.push_back(nextNode);
        return result;
    }

    void printPath(std::string word, std::deque<std::pair<int,int> >removedNodes)
    {
        int pathNodes[word.size()]; /// the correct path nodes (the last removed nodes per place
        /// in the word, because if an index was removed multiple times it means the path didn't
        /// lead to the end for all but the last one)

        for (const auto& node : removedNodes)
            pathNodes[node.second] = node.first; /// second = i, index of letter; first = node

        std::deque< int > result;
        result.push_back(pathNodes[0]); /// should be the start node.

        for(unsigned int i=1;i<=word.size();i++)
        {
            if(edges[result.back()][word[i-1]].find(pathNodes[i])
               != edges[result.back()][word[i-1]].end())
            { /// if there is a edge between previous node and current one
                result.push_back(pathNodes[i]);
                continue;
            }

            /// now we know we used lambdas to get to node[i] so we need to find it.
            std::deque<int> lambdaPath = getLambdaPath(result.back(),word[i-1],pathNodes[i]);

            while(!lambdaPath.empty())
            {
                result.push_back(lambdaPath.front());
                lambdaPath.pop_front();
            }
        }

        while(!result.empty())
        {
            std::cout << result.front() << ' ' ;
            result.pop_front();
        }
    }
    bool acceptEmpty()
    {
        if(finalStates.find(startState) != finalStates.end())
            return true; /// if the start node is also a final node.
        for(const auto& lambdaNode:edges[startState][0])
            if(finalStates.find(lambdaNode) != finalStates.end())
                return true;
        return false;
    }

public:

    using FA::runTests;
    bool accepted(std::string word, bool outputPath = false)
    {
        if(word.empty()) /// special case
            return acceptEmpty();

        std::stack<std::pair<int,int> > stk; /// remembers the nodes and the index of the added nodes
        /// to the iterative depth first search "simulated" stack
        stk.push({startState,0});

        std::deque<std::pair<int,int> >  removedNodes; /// remembers the nodes and the index of the popped nodes.
        ///`Used for rebuilding and printing the path.

        while(!stk.empty())
        {
            std::unordered_set<int> same,vis; /// "same" is for nodes reachable with a lambda path
            /// and "vis" for nodes that can be visited on the next
            int node = stk.top().first;
            unsigned int i = stk.top().second;

            removedNodes.push_back(stk.top());
            stk.pop();

            if(i == word.size())
            {/// reached the end of the word. Finish or backtrack
                if(finalStates.find(node) != finalStates.end())
                {
                    if(outputPath)
                        printPath(word, removedNodes);
                    return true;
                }

                continue;
            }

            std::stack<int> startNodes; /// nodes that can be reached by lambda paths (start next edge)
            startNodes.push(node);
            same.insert(node);

            /// calcualtes the set of nodes which we can begin from
            while(!startNodes.empty())
            {
                int sameNode = startNodes.top();
                startNodes.pop();
                /// add all new lambda edges to the set (and to be verified).
                for (const auto& nextNode:edges[node]['0'])
                {
                    if(same.find(nextNode) == same.end())
                    {
                        same.insert(nextNode);
                        startNodes.push(nextNode);
                    }
                }

                /// add the new edges to the next visitable set.
                for (const auto& nextNode:edges[sameNode][word[i]])
                    vis.insert(nextNode);
            }

            /// adds all the reachable nodes.
            for (const auto& nextNode:vis)
                stk.push({nextNode,i+1});
        }
        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
    l_NFA automata;
    fin >> automata;
    automata.runTests(fin,fout,false);
}