/// 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);
        }
    }
    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 NFA : public FA{
public:
    using FA::runTests;
    void path(std::string word){
        accepted(word,true);
    }
    void printPath(const std::vector<int>& nodes, std::string word){
    }
    bool acceptedEmpty(bool outputPath = false){ /// handles empty word
        if(finalStates.find(startState) == finalStates.end())
            return false;
        if(outputPath)
            std::cout << startState;
        return true;
    }
    bool accepted(std::string word, bool outputPath = false){
        if(word.empty()) /// special case
            return acceptedEmpty(outputPath);

        std::unordered_set<int> visited[word.size() + 2]; /// which nodes have been visited for each letter to
        /// not compute the same thing multiple times. Costs O(word.size * nr_states) space worst case.

        std::vector<int> solutionNodes(word.size()+2);
        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});

        while(!stk.empty()){
            int node = stk.top().first;
            unsigned int i = stk.top().second;
            stk.pop();

            solutionNodes[i] = node; /// position i will be rewritten if dfs backtracks.

            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(finalStates.find(node) == finalStates.end())
                    continue;
                if(outputPath)
                    printPath(solutionNodes,word);
                return true;
            }

            for (const auto& nextNode:edges[node][word[i]])
                stk.push({nextNode,i+1});
        }
        return false;
    }
};
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();
    }
    
    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;
        throw std::logic_error("NoFinishNodeFound");
    }

    bool acceptedEmpty(bool outputPath = false){
        if(!isFinishReachable(startState))
            return false;
        if(!outputPath)
            return true;

        std::deque<int> path = getLambdaPath(startState,getFinishNode(startState));
        if(finalStates.find(startState) != finalStates.end())
            path.push_back(startState);
        while(!path.empty()){
            std::cout << path.front();
            path.pop_front();
            if(!path.empty())
                std::cout << " -@-> ";
        }
        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.
                if(outputPath)
                    printPath(word, removedNodes);
                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;
    }
    NFA to_NFA();
};
NFA l_NFA::to_NFA()
{
    FA original; /// keep old data to copy it back.
    original.set_FA(this->get_FA());

    std::deque<int> nodes; /// all nodes(states) that have transitions
    for(const auto& edge:edges)
        nodes.push_back(edge.first);

    for(const auto& node:nodes)
    {
        std::unordered_set<int> reachable = getReachableLambda(node);
        edges[node][LAMBDA].clear();

        for(const auto& sameNode:reachable){
            if(finalStates.find(sameNode) != finalStates.end())
                finalStates.insert(node);
            for(const auto& edge:edges[sameNode])
            {
                if(edge.first == LAMBDA)
                    continue;
                for(const auto& newNode:edge.second)
                    edges[node][edge.first].insert(newNode);
            }
        }
    }

    NFA result;
    result.set_FA(this->get_FA());
    this->set_FA(original.get_FA());
    return result;
}
int main()
{
    std::ifstream fin("nfa.in");
    std::ofstream fout("nfa.out");
    l_NFA automata;
    fin >> automata;
    NFA convNFA = automata.to_NFA();
    convNFA.runTests(fin,fout);
}