/// un cod FOARTE LUNG care respecta toate cerintele si individualizate,
/// implementand algoritmi relativ eficienti pe DFA, NFA, lambda-NFA.
/// (facut de Pescariu Matei-Alexandru - tema 1 LFA).
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <vector>

class FA{ /// abstract implementation of a finite automata
protected:
    const char LAMBDA = '@'; /// the character decided to be lambda/epsilon/empty symbol.
    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<int> is used for lambdaNFAs to search for the lambda transition. It also is compatible with DFA/NFA.

    virtual void path(std::string word) {}/// displays path in console. MUST be implemented in derived classes.
    void runTests(std::istream& in,std::ostream& out){ /// 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)
            }
            else{
                out << "0\n"; /// means No
            }
        }
    }
public:
    FA(){}
    FA(const FA& fa){set_FA(fa);}
    void set_FA(FA newFa){startState = newFa.startState; finalStates = newFa.finalStates; edges = newFa.edges;}
    FA get_FA(){ /// gets base common variables (needed in derived classes).
        FA result;
        result.startState = startState;
        result.finalStates = finalStates;
        result.edges = edges;
        return result;
    }
    void read(std::istream& in){/// input data format is present in requirements.txt
        int n,m;
        std::deque<int> states;
        std::string listFinals;
        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 n1,n2;
            char l;
            in >> n1 >> n2 >> l;
            edges[n1][l].insert(n2);
        }
    }
    virtual bool accepted(std::string word, bool a = false){return false;} /// MUST be 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; /// used read so I could write that inside the class.
}

class l_NFA : public FA{ /// the lambda non deterministic finite automata. The most important one, NFAs and DFAs being special cases of this.
protected:
    void path(std::string word){ accepted(word,true); }
    bool checkTransition(int prevNode,char c,int nextNode){ /// checks if transition exists.
        return edges.find(prevNode) != edges.end() &&
               edges[prevNode].find(c) != edges[prevNode].end() &&
               edges[prevNode][c].find(nextNode) != edges[prevNode][c].end();
    }
    int getLambdaLast(int prevNode,char c,int nextNode){ /// gets a lambda reachable node that has a transition c to nextNode.
        std::unordered_set<int> same = getReachableLambda(prevNode);
        for(const auto& sameNode:same){
            if(!checkTransition(sameNode,c,nextNode))
                continue;
            return sameNode;
        }
        return prevNode;
    }
    std::unordered_map<int,int> getLambdaPrevious(int startNode){ /// allows computation of lambda paths by saying which
        /// node we reached the current node from.

        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[startNode] = startNode; /// to figure out it's the first one.

        std::stack<int> stk;
        stk.push(startNode);
        while(!stk.empty()){
            int node = stk.top();
            stk.pop();

            for (const auto& sameNode:edges[node][LAMBDA]){ /// 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; /// reached it from the node called node.
            }
        }
        return lambdaPath;
    }
    std::unordered_set<int> getReachableLambda(int node){
        std::unordered_set<int> same;
        auto reachableFrom = getLambdaPrevious(node);
        for(const auto& sameNode:reachableFrom)
            same.insert(sameNode.first);
        return same;
    }
    bool isFinishReachable(int node){
        return (finalStates.find(getFinishNode(node)) != finalStates.end());
    }
    int getFinishNode(int node){
        if(finalStates.find(node) != finalStates.end())
            return node;
        std::unordered_set<int> same = getReachableLambda(node);
        for(const auto& lambdaNode:same)
            if(finalStates.find(lambdaNode) != finalStates.end())
                return lambdaNode;
        return node;
    }

    bool acceptedEmpty(bool outputPath = false){
        if(!isFinishReachable(startState))
            return false;
        return true;
    }
public:
    using FA::runTests;
    bool accepted(std::string word, bool outputPath = false){
        std::unordered_set<int> visited[word.size() + 2];

        if(word.empty()) /// special case
            return acceptedEmpty(outputPath);

        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())
        {
            int node = stk.top().first;
            unsigned int i = stk.top().second;
            removedNodes.push_back(stk.top());
            stk.pop();

            if(visited[i].find(node) != visited[i].end())
                continue;
            visited[i].insert(node);

            if(i == word.size())
            {/// reached the end of the word. Finish or backtrack
                if(!isFinishReachable(node))
                    continue; /// don't add next transitions.
                return true;
            }

            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
            same = getReachableLambda(node);

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

            /// adds all the reachable nodes.
            for (const auto& nextNode:vis)
                stk.push({nextNode,i+1});
        }
        return false;
    }
};
int main()
{
    std::ifstream fin("nfa.in");
    std::ofstream fout("nfa.out");
    l_NFA automata;
    fin >> automata;
    ///NFA convNFA = automata.to_NFA();
    automata.runTests(fin,fout);
}