#include <vector>
#include <string>
#include <algorithm>

char int51[51][10] = {{0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,1,1,'c'},
    {1,0,0,0,0,0,0,0,1,'e'},
    {0,1,0,0,0,0,0,1,2,'c'},
    {1,0,0,0,0,0,1,0,2,'e'},
    {1,0,0,1,0,0,0,0,2,'k'},
    {1,0,0,0,0,0,0,1,2,'a'},
    {1,0,0,0,1,0,0,0,2,'i'},
    {0,0,0,1,0,0,0,1,2,'n'},
    {0,1,0,1,0,0,0,1,3,'c'},
    {1,0,1,0,0,0,1,0,3,'e'},
    {1,0,0,1,0,0,1,0,3,'k'},
    {1,0,0,0,0,0,1,1,3,'a'},
    {0,0,0,0,0,1,1,1,3,'i'},
    {0,1,0,0,0,0,1,1,3,'n'},
    {0,1,0,0,1,0,0,1,3,'y'},
    {0,0,0,1,0,0,1,1,3,'q'},
    {0,1,1,0,1,0,0,0,3,'j'},
    {1,1,0,0,1,0,0,0,3,'r'},
    {0,1,0,1,0,1,0,1,4,'c'},
    {1,0,1,0,1,0,1,0,4,'e'},
    {1,1,0,1,0,0,1,0,4,'k'},
    {0,0,0,0,1,1,1,1,4,'a'},
    {0,1,1,0,0,0,1,1,4,'i'},
    {0,0,0,1,0,1,1,1,4,'n'},
    {0,1,0,0,1,1,0,1,4,'y'},
    {1,0,0,1,0,0,1,1,4,'q'},
    {0,1,1,0,1,0,1,0,4,'j'},
    {1,1,1,0,1,0,0,0,4,'r'},
    {1,1,0,0,1,0,0,1,4,'t'},
    {0,0,0,1,1,0,1,1,4,'w'},
    {1,0,0,1,1,0,0,1,4,'z'},
    {1,0,1,0,1,1,1,0,5,'c'},
    {0,1,0,1,1,1,0,1,5,'e'},
    {0,1,1,0,1,1,0,1,5,'k'},
    {0,1,1,1,1,1,0,0,5,'a'},
    {1,1,1,1,1,0,0,0,5,'i'},
    {1,0,1,1,1,1,0,0,5,'n'},
    {1,0,1,1,0,1,1,0,5,'y'},
    {1,1,1,0,1,1,0,0,5,'q'},
    {1,0,0,1,0,1,1,1,5,'j'},
    {0,0,1,1,0,1,1,1,5,'r'},
    {1,0,1,1,1,1,1,0,6,'c'},
    {0,1,1,1,1,1,0,1,6,'e'},
    {0,1,1,0,1,1,1,1,6,'k'},
    {0,1,1,1,1,1,1,0,6,'a'},
    {0,1,1,1,0,1,1,1,6,'i'},
    {1,1,1,0,1,1,1,0,6,'n'},
    {1,1,1,1,1,1,1,0,7,'c'},
    {0,1,1,1,1,1,1,1,7,'e'},
    {1,1,1,1,1,1,1,1,8,8}};
char int256[256][10] = {
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,1,1,'c'},
    {0,0,0,0,0,0,1,0,1,'e'},
    {0,0,0,0,0,0,1,1,2,'a'},
    {0,0,0,0,0,1,0,0,1,'c'},
    {0,0,0,0,0,1,0,1,2,'c'},
    {0,0,0,0,0,1,1,0,2,'a'},
    {0,0,0,0,0,1,1,1,3,'i'},
    {0,0,0,0,1,0,0,0,1,'e'},
    {0,0,0,0,1,0,0,1,2,'k'},
    {0,0,0,0,1,0,1,0,2,'e'},
    {0,0,0,0,1,0,1,1,3,'j'},
    {0,0,0,0,1,1,0,0,2,'a'},
    {0,0,0,0,1,1,0,1,3,'n'},
    {0,0,0,0,1,1,1,0,3,'a'},
    {0,0,0,0,1,1,1,1,4,'a'},
    {0,0,0,1,0,0,0,0,1,'c'},
    {0,0,0,1,0,0,0,1,2,'n'},
    {0,0,0,1,0,0,1,0,2,'k'},
    {0,0,0,1,0,0,1,1,3,'q'},
    {0,0,0,1,0,1,0,0,2,'c'},
    {0,0,0,1,0,1,0,1,3,'c'},
    {0,0,0,1,0,1,1,0,3,'n'},
    {0,0,0,1,0,1,1,1,4,'n'},
    {0,0,0,1,1,0,0,0,2,'a'},
    {0,0,0,1,1,0,0,1,3,'q'},
    {0,0,0,1,1,0,1,0,3,'j'},
    {0,0,0,1,1,0,1,1,4,'w'},
    {0,0,0,1,1,1,0,0,3,'i'},
    {0,0,0,1,1,1,0,1,4,'n'},
    {0,0,0,1,1,1,1,0,4,'a'},
    {0,0,0,1,1,1,1,1,5,'a'},
    {0,0,1,0,0,0,0,0,1,'e'},
    {0,0,1,0,0,0,0,1,2,'k'},
    {0,0,1,0,0,0,1,0,2,'i'},
    {0,0,1,0,0,0,1,1,3,'r'},
    {0,0,1,0,0,1,0,0,2,'k'},
    {0,0,1,0,0,1,0,1,3,'y'},
    {0,0,1,0,0,1,1,0,3,'r'},
    {0,0,1,0,0,1,1,1,4,'t'},
    {0,0,1,0,1,0,0,0,2,'e'},
    {0,0,1,0,1,0,0,1,3,'k'},
    {0,0,1,0,1,0,1,0,3,'e'},
    {0,0,1,0,1,0,1,1,4,'j'},
    {0,0,1,0,1,1,0,0,3,'j'},
    {0,0,1,0,1,1,0,1,4,'k'},
    {0,0,1,0,1,1,1,0,4,'r'},
    {0,0,1,0,1,1,1,1,5,'n'},
    {0,0,1,1,0,0,0,0,2,'a'},
    {0,0,1,1,0,0,0,1,3,'q'},
    {0,0,1,1,0,0,1,0,3,'r'},
    {0,0,1,1,0,0,1,1,4,'z'},
    {0,0,1,1,0,1,0,0,3,'n'},
    {0,0,1,1,0,1,0,1,4,'y'},
    {0,0,1,1,0,1,1,0,4,'i'},
    {0,0,1,1,0,1,1,1,5,'r'},
    {0,0,1,1,1,0,0,0,3,'a'},
    {0,0,1,1,1,0,0,1,4,'q'},
    {0,0,1,1,1,0,1,0,4,'r'},
    {0,0,1,1,1,0,1,1,5,'q'},
    {0,0,1,1,1,1,0,0,4,'a'},
    {0,0,1,1,1,1,0,1,5,'j'},
    {0,0,1,1,1,1,1,0,5,'i'},
    {0,0,1,1,1,1,1,1,6,'a'},
    {0,1,0,0,0,0,0,0,1,'c'},
    {0,1,0,0,0,0,0,1,2,'c'},
    {0,1,0,0,0,0,1,0,2,'k'},
    {0,1,0,0,0,0,1,1,3,'n'},
    {0,1,0,0,0,1,0,0,2,'n'},
    {0,1,0,0,0,1,0,1,3,'c'},
    {0,1,0,0,0,1,1,0,3,'q'},
    {0,1,0,0,0,1,1,1,4,'n'},
    {0,1,0,0,1,0,0,0,2,'k'},
    {0,1,0,0,1,0,0,1,3,'y'},
    {0,1,0,0,1,0,1,0,3,'k'},
    {0,1,0,0,1,0,1,1,4,'k'},
    {0,1,0,0,1,1,0,0,3,'q'},
    {0,1,0,0,1,1,0,1,4,'y'},
    {0,1,0,0,1,1,1,0,4,'q'},
    {0,1,0,0,1,1,1,1,5,'j'},
    {0,1,0,1,0,0,0,0,2,'c'},
    {0,1,0,1,0,0,0,1,3,'c'},
    {0,1,0,1,0,0,1,0,3,'y'},
    {0,1,0,1,0,0,1,1,4,'y'},
    {0,1,0,1,0,1,0,0,3,'c'},
    {0,1,0,1,0,1,0,1,4,'c'},
    {0,1,0,1,0,1,1,0,4,'y'},
    {0,1,0,1,0,1,1,1,5,'e'},
    {0,1,0,1,1,0,0,0,3,'n'},
    {0,1,0,1,1,0,0,1,4,'y'},
    {0,1,0,1,1,0,1,0,4,'k'},
    {0,1,0,1,1,0,1,1,5,'k'},
    {0,1,0,1,1,1,0,0,4,'n'},
    {0,1,0,1,1,1,0,1,5,'e'},
    {0,1,0,1,1,1,1,0,5,'j'},
    {0,1,0,1,1,1,1,1,6,'e'},
    {0,1,1,0,0,0,0,0,2,'a'},
    {0,1,1,0,0,0,0,1,3,'n'},
    {0,1,1,0,0,0,1,0,3,'r'},
    {0,1,1,0,0,0,1,1,4,'i'},
    {0,1,1,0,0,1,0,0,3,'q'},
    {0,1,1,0,0,1,0,1,4,'y'},
    {0,1,1,0,0,1,1,0,4,'z'},
    {0,1,1,0,0,1,1,1,5,'r'},
    {0,1,1,0,1,0,0,0,3,'j'},
    {0,1,1,0,1,0,0,1,4,'k'},
    {0,1,1,0,1,0,1,0,4,'j'},
    {0,1,1,0,1,0,1,1,5,'y'},
    {0,1,1,0,1,1,0,0,4,'w'},
    {0,1,1,0,1,1,0,1,5,'k'},
    {0,1,1,0,1,1,1,0,5,'q'},
    {0,1,1,0,1,1,1,1,6,'k'},
    {0,1,1,1,0,0,0,0,3,'i'},
    {0,1,1,1,0,0,0,1,4,'n'},
    {0,1,1,1,0,0,1,0,4,'t'},
    {0,1,1,1,0,0,1,1,5,'r'},
    {0,1,1,1,0,1,0,0,4,'n'},
    {0,1,1,1,0,1,0,1,5,'e'},
    {0,1,1,1,0,1,1,0,5,'r'},
    {0,1,1,1,0,1,1,1,6,'i'},
    {0,1,1,1,1,0,0,0,4,'a'},
    {0,1,1,1,1,0,0,1,5,'j'},
    {0,1,1,1,1,0,1,0,5,'n'},
    {0,1,1,1,1,0,1,1,6,'k'},
    {0,1,1,1,1,1,0,0,5,'a'},
    {0,1,1,1,1,1,0,1,6,'e'},
    {0,1,1,1,1,1,1,0,6,'a'},
    {0,1,1,1,1,1,1,1,7,'e'},
    {1,0,0,0,0,0,0,0,1,'e'},
    {1,0,0,0,0,0,0,1,2,'a'},
    {1,0,0,0,0,0,1,0,2,'e'},
    {1,0,0,0,0,0,1,1,3,'a'},
    {1,0,0,0,0,1,0,0,2,'k'},
    {1,0,0,0,0,1,0,1,3,'n'},
    {1,0,0,0,0,1,1,0,3,'j'},
    {1,0,0,0,0,1,1,1,4,'a'},
    {1,0,0,0,1,0,0,0,2,'i'},
    {1,0,0,0,1,0,0,1,3,'r'},
    {1,0,0,0,1,0,1,0,3,'e'},
    {1,0,0,0,1,0,1,1,4,'r'},
    {1,0,0,0,1,1,0,0,3,'r'},
    {1,0,0,0,1,1,0,1,4,'i'},
    {1,0,0,0,1,1,1,0,4,'r'},
    {1,0,0,0,1,1,1,1,5,'i'},
    {1,0,0,1,0,0,0,0,2,'k'},
    {1,0,0,1,0,0,0,1,3,'q'},
    {1,0,0,1,0,0,1,0,3,'k'},
    {1,0,0,1,0,0,1,1,4,'q'},
    {1,0,0,1,0,1,0,0,3,'y'},
    {1,0,0,1,0,1,0,1,4,'y'},
    {1,0,0,1,0,1,1,0,4,'k'},
    {1,0,0,1,0,1,1,1,5,'j'},
    {1,0,0,1,1,0,0,0,3,'r'},
    {1,0,0,1,1,0,0,1,4,'z'},
    {1,0,0,1,1,0,1,0,4,'j'},
    {1,0,0,1,1,0,1,1,5,'q'},
    {1,0,0,1,1,1,0,0,4,'t'},
    {1,0,0,1,1,1,0,1,5,'r'},
    {1,0,0,1,1,1,1,0,5,'n'},
    {1,0,0,1,1,1,1,1,6,'a'},
    {1,0,1,0,0,0,0,0,2,'e'},
    {1,0,1,0,0,0,0,1,3,'j'},
    {1,0,1,0,0,0,1,0,3,'e'},
    {1,0,1,0,0,0,1,1,4,'r'},
    {1,0,1,0,0,1,0,0,3,'k'},
    {1,0,1,0,0,1,0,1,4,'k'},
    {1,0,1,0,0,1,1,0,4,'j'},
    {1,0,1,0,0,1,1,1,5,'n'},
    {1,0,1,0,1,0,0,0,3,'e'},
    {1,0,1,0,1,0,0,1,4,'j'},
    {1,0,1,0,1,0,1,0,4,'e'},
    {1,0,1,0,1,0,1,1,5,'c'},
    {1,0,1,0,1,1,0,0,4,'j'},
    {1,0,1,0,1,1,0,1,5,'y'},
    {1,0,1,0,1,1,1,0,5,'c'},
    {1,0,1,0,1,1,1,1,6,'c'},
    {1,0,1,1,0,0,0,0,3,'j'},
    {1,0,1,1,0,0,0,1,4,'w'},
    {1,0,1,1,0,0,1,0,4,'j'},
    {1,0,1,1,0,0,1,1,5,'q'},
    {1,0,1,1,0,1,0,0,4,'k'},
    {1,0,1,1,0,1,0,1,5,'k'},
    {1,0,1,1,0,1,1,0,5,'y'},
    {1,0,1,1,0,1,1,1,6,'k'},
    {1,0,1,1,1,0,0,0,4,'r'},
    {1,0,1,1,1,0,0,1,5,'q'},
    {1,0,1,1,1,0,1,0,5,'c'},
    {1,0,1,1,1,0,1,1,6,'n'},
    {1,0,1,1,1,1,0,0,5,'n'},
    {1,0,1,1,1,1,0,1,6,'k'},
    {1,0,1,1,1,1,1,0,6,'c'},
    {1,0,1,1,1,1,1,1,7,'c'},
    {1,1,0,0,0,0,0,0,2,'a'},
    {1,1,0,0,0,0,0,1,3,'i'},
    {1,1,0,0,0,0,1,0,3,'j'},
    {1,1,0,0,0,0,1,1,4,'a'},
    {1,1,0,0,0,1,0,0,3,'q'},
    {1,1,0,0,0,1,0,1,4,'n'},
    {1,1,0,0,0,1,1,0,4,'w'},
    {1,1,0,0,0,1,1,1,5,'a'},
    {1,1,0,0,1,0,0,0,3,'r'},
    {1,1,0,0,1,0,0,1,4,'t'},
    {1,1,0,0,1,0,1,0,4,'j'},
    {1,1,0,0,1,0,1,1,5,'n'},
    {1,1,0,0,1,1,0,0,4,'z'},
    {1,1,0,0,1,1,0,1,5,'r'},
    {1,1,0,0,1,1,1,0,5,'q'},
    {1,1,0,0,1,1,1,1,6,'a'},
    {1,1,0,1,0,0,0,0,3,'n'},
    {1,1,0,1,0,0,0,1,4,'n'},
    {1,1,0,1,0,0,1,0,4,'k'},
    {1,1,0,1,0,0,1,1,5,'j'},
    {1,1,0,1,0,1,0,0,4,'y'},
    {1,1,0,1,0,1,0,1,5,'e'},
    {1,1,0,1,0,1,1,0,5,'k'},
    {1,1,0,1,0,1,1,1,6,'e'},
    {1,1,0,1,1,0,0,0,4,'i'},
    {1,1,0,1,1,0,0,1,5,'r'},
    {1,1,0,1,1,0,1,0,5,'y'},
    {1,1,0,1,1,0,1,1,6,'k'},
    {1,1,0,1,1,1,0,0,5,'r'},
    {1,1,0,1,1,1,0,1,6,'i'},
    {1,1,0,1,1,1,1,0,6,'k'},
    {1,1,0,1,1,1,1,1,7,'e'},
    {1,1,1,0,0,0,0,0,3,'a'},
    {1,1,1,0,0,0,0,1,4,'a'},
    {1,1,1,0,0,0,1,0,4,'r'},
    {1,1,1,0,0,0,1,1,5,'i'},
    {1,1,1,0,0,1,0,0,4,'q'},
    {1,1,1,0,0,1,0,1,5,'j'},
    {1,1,1,0,0,1,1,0,5,'q'},
    {1,1,1,0,0,1,1,1,6,'a'},
    {1,1,1,0,1,0,0,0,4,'r'},
    {1,1,1,0,1,0,0,1,5,'n'},
    {1,1,1,0,1,0,1,0,5,'c'},
    {1,1,1,0,1,0,1,1,6,'c'},
    {1,1,1,0,1,1,0,0,5,'q'},
    {1,1,1,0,1,1,0,1,6,'k'},
    {1,1,1,0,1,1,1,0,6,'n'},
    {1,1,1,0,1,1,1,1,7,'c'},
    {1,1,1,1,0,0,0,0,4,'a'},
    {1,1,1,1,0,0,0,1,5,'a'},
    {1,1,1,1,0,0,1,0,5,'n'},
    {1,1,1,1,0,0,1,1,6,'a'},
    {1,1,1,1,0,1,0,0,5,'j'},
    {1,1,1,1,0,1,0,1,6,'e'},
    {1,1,1,1,0,1,1,0,6,'k'},
    {1,1,1,1,0,1,1,1,7,'e'},
    {1,1,1,1,1,0,0,0,5,'i'},
    {1,1,1,1,1,0,0,1,6,'a'},
    {1,1,1,1,1,0,1,0,6,'c'},
    {1,1,1,1,1,0,1,1,7,'c'},
    {1,1,1,1,1,1,0,0,6,'a'},
    {1,1,1,1,1,1,0,1,7,'e'},
    {1,1,1,1,1,1,1,0,7,'c'},
    {1,1,1,1,1,1,1,1,8,'8'}};

const char henselmap[127] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 4, 8, 2, 0, 0, 5, 0, 0, 7, 9, 0, 10, 0, 0, 11, 0, 6, 12, 0, 0, 0, 0};

struct TrLeaf {
    char num;
    char hensel;
    std::vector<std::vector<bool>> subTrs[9][13];
};
struct TrNode {
    TrLeaf leaf;
    TrNode* nextNode[2] = {nullptr,nullptr};
};

TrNode tree;

void set_up_tree(){
    TrNode * currNode;
    TrLeaf lif; TrLeaf emptyLeaf;

    bool hasSTr;
    std::vector<bool> config(8);

    for(int i = 0; i < 256 /*number of elements in int256*/; i++){
        currNode = &tree;

        //descend down the tree based on the neighborhood
        for(int j = 0; j < 8; j++){
            if((*currNode).nextNode[int256[i][j]] == nullptr){
                (*currNode).nextNode[int256[i][j]] = new TrNode();
            }
            currNode = (*currNode).nextNode[int256[i][j]];
        }

        //filling in transition info...
        lif = emptyLeaf;
        lif.num = int256[i][8];
        lif.hensel = int256[i][9];

        //getting subtransitions
        for(int j = 0; j < 256; j++){
            hasSTr = true;
            for(int k = 0; k < 8; k++){
                if(int256[j][k] == 0){
                    continue;
                }
                if(int256[j][k] != int256[i][k]){
                    hasSTr = false;
                    break;
                }
            }
            if(hasSTr){
                for(int k = 0; k < 8; k++){
                    config[k] = int256[j][k];
                }
                if((lif.num == 0 && int256[j][8] == 0) || (lif.num != 0 && int256[j][8] != 0)){
                    lif.subTrs[int256[j][8]][henselmap[int256[j][9]]].push_back(config);
                }
            }
        }

        (*currNode).leaf = lif;
    }
}

struct ConstraintSection {
    std::vector<int> states;
    char num = 127;
    char hensel = 127;
};

struct SubcfgConstraintSect {
    std::vector<int> states;
    char num = 127;
    char hensel = 127;
    std::vector<SubcfgConstraintSect*> childcons;
    SubcfgConstraintSect(ConstraintSection con){
        states = con.states;
        num = con.num;
        hensel = con.hensel;
    }
    ~SubcfgConstraintSect(){
        for(int i = 0; i < childcons.size(); i++){
            if(childcons[i] != nullptr){
                delete childcons[i];
            }
        }
    }
};

struct Constraint {
    int endState;
    std::vector<ConstraintSection> sections;
    std::vector<std::vector<ConstraintSection>> subconfigs;
    std::vector<SubcfgConstraintSect*> subcfgs;
};

struct StateChanges {
    int beginState;
    std::vector<Constraint> constraints;
    std::vector<Constraint> negconstraints;
};

std::vector<StateChanges> rule;
std::vector<StateChanges> newrule;

int tempnumstates;
int numStates;

struct RtNode {
    int endState;
    RtNode** nextCell;
    RtNode(int states) {
        nextCell = new RtNode*[states+1];
        for(int i = 0; i <= states; i++){
            nextCell[i] = nullptr;
        }
    }
    ~RtNode(){
        for(int i = 0; i <= numStates; i++){
            if(nextCell[i] != nullptr){
                delete nextCell[i];
            }
        }
        delete[] nextCell;
    }
};

RtNode * ruletree = nullptr;
int maxLeaves = 160000;
int currLeaves = 0;

bool valid_rulestring(std::string rs){  //sets up part of the rule structure (specifically, adds however many states as the maximum state number specified in the rulestring to the structure), returns false if rulestring isn't valid
    std::string rulestring = rs + "/";
    std::string emptyStr = "";

    int numstates = 0; std::string numStr = "";
    bool stateChangeSpec = true;
    bool stateConSpec = false; int numConStates = 0;
    bool preCol = false;

    int numnums = 0; int numhensels = 0; int numnegs = 0;
    int numBSTs = 0; bool hasBST = false;
    std::vector<std::vector<int>> statesInCon;
    for(int i = 0; i < rulestring.length(); i++){   //first pass
        if(stateChangeSpec){
            if((rulestring[i]+emptyStr).find_first_of("0123456789") != -1){
                numStr = numStr + rulestring[i];
            }
            else if((rulestring[i]+emptyStr).find_first_of("BST.-/") != -1){
                if(rulestring[i] == 'B' || rulestring[i] == 'S'){
                    numBSTs++;
                    hasBST = true;
                    continue;
                }
                if(rulestring[i] == 'T' && numStr == ""){   //returns false when "T" isn't preceded by a num
                    return false;
                }
                if(stoi(numStr) > numstates){
                    numstates = stoi(numStr);
                }
                if(rulestring[i] == 'T'){
                    numBSTs++;
                    hasBST = true;
                    numStr = "";
                }
                if(rulestring[i] == '.' || rulestring[i] == '-'){
                    stateChangeSpec = false;
                    numStr = "";
                    numnegs = 0;
                    if(rulestring.find_first_of(";()./-",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1){
                        stateConSpec = true;
                        preCol = true;
                    }
                    if(rulestring[i] == '-'){
                        numnegs++;
                    }
                }
                if(numBSTs > 1){    //returns false when none of 'B', 'S', or 'T' occur in state change specification
                    return false;
                }
            }
            else{   //returns false when the wrong symbols occur in state change specification
                return false;
            }
        }
        else{
            if((rulestring[i]+emptyStr).find_first_of(";()./-:+0123456789cekainyqjrtwz") == -1){    //returns false when the wrong symbols occur in constraint specification
                return false;
            }
            if((rulestring[i]+emptyStr).find_first_of(";()./-") != -1){
                if(numnums > 1 || numhensels > 1){  //returns false when more than one hensel or num occurs in subconstraint
                    return false;
                }
                numnums = 0;
                numhensels = 0;
                if(rulestring[i] == '-'){
                    numnegs++;
                }
                if(numnegs > 1){    
                    return false;
                }
                if(!stateConSpec){
                    if(numConStates > numstates){
                        numstates = numConStates;
                    }
                    if(rulestring[i] == ';'){
                        numConStates++;
                    }
                    else{
                        numConStates = 0;
                    }
                }
                if(rulestring.find_first_of(";()./-",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1){
                    stateConSpec = true;
                }
                if(stateConSpec){
                    if(preCol){
                        return false;
                    }
                    preCol = true;
                }
            }
            if((rulestring[i]+emptyStr).find_first_of("()./-") != -1 && !(rulestring.find_first_of(";()./-",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1)){
                stateConSpec = false;
                preCol = false;
            }
            if(preCol && (rulestring[i]+emptyStr).find_first_of(";()./-") == -1){
                if(rulestring[i] == ':'){
                    if(rulestring.find_first_of(";()./",i+1) > rulestring.find(':',i+1) && rulestring.find(':',i) != -1){
                        return false;
                    }
                    preCol = false;
                    if(numStr == ""){
                        return false;
                    }
                    numConStates = stoi(numStr);
                    if(numConStates > numstates){
                        numstates = numConStates;
                    }
                    numStr = "";
                }
                else if(rulestring[i] == '+'){
                    if(numStr == ""){
                        return false;
                    }
                    numConStates = stoi(numStr);
                    if(numConStates > numstates){
                        numstates = numConStates;
                    }
                    numStr = "";
                }
                else if((rulestring[i]+emptyStr).find_first_of("0123456789") != -1){
                    numStr = numStr + rulestring[i];
                }
                else{
                    return false;
                }
            }
            else if((rulestring[i]+emptyStr).find_first_of(";()./-") == -1){
                if((rulestring[i]+emptyStr).find_first_of("012345678") != -1){
                    numnums++;
                }
                else if((rulestring[i]+emptyStr).find_first_of("cekainyqjrtwz") != -1){
                    numhensels++;
                }
                else{
                    return false;
                }
            }
        }
        if(rulestring[i] == '/'){
            if(!hasBST){
                return false;
            }
            stateChangeSpec = true;
            numStr = "";
            numBSTs = 0;
            hasBST = false;
        }
    }

    bool inSubcon = false;
    for(int i = 0; i < rulestring.length(); i++){
        if(rulestring[i] == '('){
            if(inSubcon){
                return false;
            }
            inSubcon = true;
        }
        else if(rulestring[i] == ')'){
            if(!inSubcon){
                return false;
            }
            inSubcon = false;
        }
        else if(inSubcon){
            if(rulestring[i] == '.' || rulestring[i] == '/' || rulestring[i] == '-'){
                return false;
            }
        }
    }

    std::vector<StateChanges> emptySC;
    newrule = emptySC;
    
    StateChanges tempsc;
    for(int i = 0; i <= numstates; i++){
        tempsc.beginState = i;
        newrule.push_back(tempsc);
    }
    tempnumstates = numstates;
    
    return true;
}
void parse_rulestring(std::string rs){
    std::string rulestring = rs + "/";
    std::string emptyStr = "";
    
    int beginState; std::string beginStateStr = ""; bool sameEnd = false;
    int endState; std::string endStateStr = "";
    bool inStateChange = true; bool doEndState = false;

    bool inConstraint = false;
    Constraint constraint; Constraint emptyConstraint;
    ConstraintSection cs; ConstraintSection emptyCS;
    std::vector<ConstraintSection> subconfig; std::vector<ConstraintSection> emptySubconfig;
    int sectionState = 0; std::string sectionStateStr = "";
    bool explicitStates = false; bool inSpecifyingStates = false;
    bool inSubconfig = false;

    bool negConstraint = false;
    bool constrained = false;
    for(int i = 0; i < rulestring.length(); i++){
        if(inStateChange){    //parse parts that indicate state changes (B1, 3T2, etc.)
            if(rulestring[i] == '.' || rulestring[i] == '-'){
                if(beginStateStr != ""){
                    beginState = stoi(beginStateStr);
                }
                endState = stoi(endStateStr);
                if(sameEnd){
                    beginState = endState;
                }
                beginStateStr = "";
                endStateStr = "";
                doEndState = false;
                sameEnd = false;
                inStateChange = false;
                inConstraint = true;
                if(rulestring[i] == '-'){
                    negConstraint = true;
                }
                if(rulestring.find_first_of(";()./-",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1){
                    explicitStates = true;
                    inSpecifyingStates = true;
                }
                continue;
            }
            if(rulestring[i] == 'T'){
                doEndState = true;
                continue;
            }
            if(!doEndState){
                if(rulestring[i] == 'B'){
                    beginState = 0;
                    doEndState = true;
                }
                else if(rulestring[i] == 'S'){
                    sameEnd = true;
                    doEndState = true;
                }
                else{
                    beginStateStr = beginStateStr + rulestring[i];
                }
            }
            else{
                endStateStr = endStateStr + rulestring[i];
            }
        }

        if(inConstraint){
            constraint.endState = endState;

            if((rulestring[i]+emptyStr).find_first_of(";()./-") != -1){
                if(!explicitStates){
                    cs.states.push_back(sectionState);
                    sectionState++;
                }

                if(rulestring.find_first_of(";()./-",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1){
                    explicitStates = true;
                }
                if(explicitStates){
                    inSpecifyingStates = true;
                }
                if(constrained){
                    if(!inSubconfig){
                        constraint.sections.push_back(cs);
                    }
                    else{
                        subconfig.push_back(cs);
                    }
                }
                constrained = false;
                cs = emptyCS;
                
            }
            if(rulestring[i] == '('){
                inSubconfig = true;
                
                if(!(rulestring.find_first_of(";()./",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1)){
                    explicitStates = false;
                    inSpecifyingStates = false;
                }
                sectionState = 0;
            }
            else if(rulestring[i] == ')'){
                constraint.subconfigs.push_back(subconfig);
                subconfig = emptySubconfig;
            }
            else if(rulestring[i] == '.' || rulestring[i] == '/' || rulestring[i] == '-'){
                if(!negConstraint){
                    newrule[beginState].constraints.push_back(constraint);
                }
                else{
                    newrule[beginState].negconstraints.push_back(constraint);
                }
                constraint = emptyConstraint;

                if(!(rulestring.find_first_of(";()./",i+1) > rulestring.find(':',i) && rulestring.find(':',i) != -1)){
                    explicitStates = false;
                    inSpecifyingStates = false;
                }
                sectionState = 0;

                inSubconfig = false;
            }
            if(rulestring[i] == '-'){
                negConstraint = true;
            }

            if(inSpecifyingStates && (rulestring[i]+emptyStr).find_first_of(";()./-") == -1){
                if(rulestring[i] == ':'){
                    inSpecifyingStates = false;
                    cs.states.push_back(stoi(sectionStateStr));
                    sectionStateStr = "";
                }
                else if(rulestring[i] == '+'){
                    cs.states.push_back(stoi(sectionStateStr));
                    sectionStateStr = "";
                }
                else{
                    sectionStateStr = sectionStateStr + rulestring[i];
                }
            }
            else{
                if((rulestring[i]+emptyStr).find_first_of("012345678") != -1){
                    cs.num = stoi(rulestring[i]+emptyStr);
                    constrained = true;
                }
                else if((rulestring[i]+emptyStr).find_first_of("cekainyqjrtwz") != -1){
                    cs.hensel = rulestring[i];
                    constrained = true;
                }
            }
        }
        if(rulestring[i] == '/'){
            inConstraint = false;
            inStateChange = true;
            negConstraint = false;
            beginStateStr = "";
            endStateStr = "";
            doEndState = false;
            sameEnd = false;
        }
    }
}
void process_rule(){

    int largest = 0;
    std::vector<ConstraintSection> temp; std::vector<ConstraintSection> empty;
    for(int i = 0;i < rule.size(); i++){
        for(int j = 0; j < rule[i].constraints.size(); j++){
            for(int k = 0; k < rule[i].constraints[j].subconfigs.size(); k++){
                for(int l = 0; l < rule[i].constraints[j].subconfigs[k].size(); l++){
                    if(rule[i].constraints[j].subconfigs[k][l].states.size() > largest){
                        largest = rule[i].constraints[j].subconfigs[k][l].states.size();
                    }
                }
                while(largest > 0){
                    for(int l = 0; l < rule[i].constraints[j].subconfigs[k].size(); l++){
                        if(rule[i].constraints[j].subconfigs[k][l].states.size() == largest){
                            temp.push_back(rule[i].constraints[j].subconfigs[k][l]);
                        }
                    }
                    largest--;
                }
                rule[i].constraints[j].subconfigs[k] = temp;
                temp = empty;
            }
        }
        for(int j = 0; j < rule[i].negconstraints.size(); j++){
            for(int k = 0; k < rule[i].negconstraints[j].subconfigs.size(); k++){
                for(int l = 0; l < rule[i].negconstraints[j].subconfigs[k].size(); l++){
                    if(rule[i].negconstraints[j].subconfigs[k][l].states.size() > largest){
                        largest = rule[i].negconstraints[j].subconfigs[k][l].states.size();
                    }
                }
                while(largest > 0){
                    for(int l = 0; l < rule[i].negconstraints[j].subconfigs[k].size(); l++){
                        if(rule[i].negconstraints[j].subconfigs[k][l].states.size() == largest){
                            temp.push_back(rule[i].negconstraints[j].subconfigs[k][l]);
                        }
                    }
                    largest--;
                }
                rule[i].negconstraints[j].subconfigs[k] = temp;
                temp = empty;
            }
        }
    }
}
void p2_helper(SubcfgConstraintSect * curr, ConstraintSection &cs){
    bool bottom = true;
    bool inthere = true;
    for(int i = 0; i < curr->childcons.size(); i++){
        inthere = true;
        for(int j = 0; j < cs.states.size(); j++){
            if(std::find(curr->childcons[i]->states.begin(),curr->childcons[i]->states.end(),cs.states[j]) == curr->childcons[i]->states.end()){
                inthere = false;
                break;
            }
        }
        if(inthere){
            bottom = false;
            p2_helper(curr->childcons[i],cs);
        }
    }
    if(bottom){
        curr->childcons.push_back(new SubcfgConstraintSect(cs));
    }
}
void process_rule_p2(){
    ConstraintSection temp;
    temp.states.push_back(-1);
    for(int i = 0;i < rule.size(); i++){
        for(int j = 0; j < rule[i].constraints.size(); j++){
            for(int k = 0; k < rule[i].constraints[j].subconfigs.size(); k++){
                rule[i].constraints[j].subcfgs.push_back(new SubcfgConstraintSect(temp));
                for(int l = 0; l < rule[i].constraints[j].subconfigs[k].size(); l++){
                    p2_helper(rule[i].constraints[j].subcfgs[k],rule[i].constraints[j].subconfigs[k][l]);
                }
            }
        }
        for(int j = 0; j < rule[i].negconstraints.size(); j++){
            for(int k = 0; k < rule[i].negconstraints[j].subconfigs.size(); k++){
                rule[i].negconstraints[j].subcfgs.push_back(new SubcfgConstraintSect(temp));
                for(int l = 0; l < rule[i].negconstraints[j].subconfigs[k].size(); l++){
                    p2_helper(rule[i].negconstraints[j].subcfgs[k],rule[i].negconstraints[j].subconfigs[k][l]);
                }
            }
        }
    }
}
bool unique_states(){
    for(int i = 0;i < newrule.size(); i++){
        for(int j = 0; j < newrule[i].constraints.size(); j++){
            for(int k = 0; k < newrule[i].constraints[j].sections.size(); k++){
                for(int l = 0; l < newrule[i].constraints[j].sections[k].states.size(); l++){
                    for(int m = l + 1; m < newrule[i].constraints[j].sections[k].states.size(); m++){
                        if(newrule[i].constraints[j].sections[k].states[l] == newrule[i].constraints[j].sections[k].states[m]){
                            return false;
                        }
                    }
                }
            }
            for(int k = 0; k < newrule[i].constraints[j].subconfigs.size(); k++){
                for(int l = 0; l < newrule[i].constraints[j].subconfigs[k].size(); l++){
                    for(int m = 0; m < newrule[i].constraints[j].subconfigs[k][l].states.size(); m++){
                        for(int n = m + 1; n < newrule[i].constraints[j].subconfigs[k][l].states.size(); n++){
                            if(newrule[i].constraints[j].subconfigs[k][l].states[m] == newrule[i].constraints[j].subconfigs[k][l].states[n]){
                                return false;
                            }
                        }
                    }
                }
            }
        }
        for(int j = 0; j < newrule[i].negconstraints.size(); j++){
            for(int k = 0; k < newrule[i].negconstraints[j].sections.size(); k++){
                for(int l = 0; l < newrule[i].negconstraints[j].sections[k].states.size(); l++){
                    for(int m = l + 1; m < newrule[i].negconstraints[j].sections[k].states.size(); m++){
                        if(newrule[i].negconstraints[j].sections[k].states[l] == newrule[i].negconstraints[j].sections[k].states[m]){
                            return false;
                        }
                    }
                }
            }
            for(int k = 0; k < newrule[i].negconstraints[j].subconfigs.size(); k++){
                for(int l = 0; l < newrule[i].negconstraints[j].subconfigs[k].size(); l++){
                    for(int m = 0; m < newrule[i].negconstraints[j].subconfigs[k][l].states.size(); m++){
                        for(int n = m + 1; n < newrule[i].negconstraints[j].subconfigs[k][l].states.size(); n++){
                            if(newrule[i].negconstraints[j].subconfigs[k][l].states[m] == newrule[i].negconstraints[j].subconfigs[k][l].states[n]){
                                return false;
                            }
                        }
                    }
                }
            }
        }
    }
    bool allIn;
    for(int i = 0;i < newrule.size(); i++){
        for(int j = 0; j < newrule[i].constraints.size(); j++){
            for(int k = 0; k < newrule[i].constraints[j].sections.size(); k++){
                for(int l = k + 1; l < newrule[i].constraints[j].sections.size(); l++){
                    if(newrule[i].constraints[j].sections[k].states.size() == newrule[i].constraints[j].sections[l].states.size()){
                        allIn = true;
                        for(int m = 0 ; m < newrule[i].constraints[j].sections[l].states.size(); m++){
                            if(std::find(newrule[i].constraints[j].sections[k].states.begin(),newrule[i].constraints[j].sections[k].states.end(),newrule[i].constraints[j].sections[l].states[m]) == newrule[i].constraints[j].sections[k].states.end()){
                                allIn = false;
                            }
                        }
                        if(allIn){
                            return false;
                        }
                    }
                }
            }
            for(int k = 0; k < newrule[i].constraints[j].subconfigs.size(); k++){
                for(int l = 0; l < newrule[i].constraints[j].subconfigs[k].size(); l++){
                    for(int m = l + 1; m < newrule[i].constraints[j].subconfigs[k].size(); m++){
                        if(newrule[i].constraints[j].subconfigs[k][l].states.size() == newrule[i].constraints[j].subconfigs[k][m].states.size()){
                            allIn = true;
                            for(int n = 0; n < newrule[i].constraints[j].subconfigs[k][m].states.size(); n++){
                                if(std::find(newrule[i].constraints[j].subconfigs[k][l].states.begin(),newrule[i].constraints[j].subconfigs[k][l].states.end(),newrule[i].constraints[j].subconfigs[k][m].states[n]) == newrule[i].constraints[j].subconfigs[k][l].states.end()){
                                    allIn = false;
                                }
                            }
                            if(allIn){
                                return false;
                            }
                        }
                    }
                }
            }
        }
        for(int j = 0; j < newrule[i].negconstraints.size(); j++){
            for(int k = 0; k < newrule[i].negconstraints[j].sections.size(); k++){
                for(int l = k + 1; l < newrule[i].negconstraints[j].sections.size(); l++){
                    if(newrule[i].negconstraints[j].sections[k].states.size() == newrule[i].negconstraints[j].sections[l].states.size()){
                        allIn = true;
                        for(int m = 0 ; m < newrule[i].negconstraints[j].sections[l].states.size(); m++){
                            if(std::find(newrule[i].negconstraints[j].sections[k].states.begin(),newrule[i].negconstraints[j].sections[k].states.end(),newrule[i].negconstraints[j].sections[l].states[m]) == newrule[i].negconstraints[j].sections[k].states.end()){
                                allIn = false;
                            }
                        }
                        if(allIn){
                            return false;
                        }
                    }
                }
            }
            for(int k = 0; k < newrule[i].negconstraints[j].subconfigs.size(); k++){
                for(int l = 0; l < newrule[i].negconstraints[j].subconfigs[k].size(); l++){
                    for(int m = l + 1; m < newrule[i].negconstraints[j].subconfigs[k].size(); m++){
                        if(newrule[i].negconstraints[j].subconfigs[k][l].states.size() == newrule[i].negconstraints[j].subconfigs[k][m].states.size()){
                            allIn = true;
                            for(int n = 0; n < newrule[i].negconstraints[j].subconfigs[k][m].states.size(); n++){
                                if(std::find(newrule[i].negconstraints[j].subconfigs[k][l].states.begin(),newrule[i].negconstraints[j].subconfigs[k][l].states.end(),newrule[i].negconstraints[j].subconfigs[k][m].states[n]) == newrule[i].negconstraints[j].subconfigs[k][l].states.end()){
                                    allIn = false;
                                }
                            }
                            if(allIn){
                                return false;
                            }
                        }
                    }
                }
            }
        }
    }
    return true;
}


void mask_neighborhood(int * nh, bool * target, std::vector<int> &unmaskedStates){
    bool isUnmasked;
    for(int i = 0; i < 8; i++){
        isUnmasked = false;
        for(int j = 0; j < unmaskedStates.size(); j++){
            if(nh[i] == unmaskedStates[j]){
                isUnmasked = true;
                break;
            }
        }
        target[i] = isUnmasked;
    }
}
bool has_subconstraint(int * nh, ConstraintSection &cs){
    bool maskednh[8];
    mask_neighborhood(nh,maskednh,cs.states);
    TrNode * currNode = &tree;
    for(int i = 0; i < 8; i++){
        currNode = currNode->nextNode[maskednh[i]];
    }
    if(cs.num != 127 && cs.num != currNode->leaf.num){
        return false;
    }
    if(cs.hensel != 127 && cs.hensel != currNode->leaf.hensel){
        return false;
    }
    return true;
}
void semi_mask(int * nh, int * target, std::vector<bool> &mask){
    for(int i = 0; i < 8; i++){
        if(mask[i]){
            target[i] = nh[i];
        }
        else{
            target[i] = -1;
        }
    }
}
bool in_subconfig(int * nh, SubcfgConstraintSect * subconfig, std::vector<bool> mask = {true,true,true,true,true,true,true,true}){
    TrNode * currTree = &tree;
    int maskedNH[8];
    bool doubleMasked[8];
    std::vector<std::vector<bool>> submasks;
    semi_mask(nh,maskedNH,mask);
    mask_neighborhood(maskedNH,doubleMasked,subconfig->states);
    for(int i = 0; i < 8; i++){
        currTree = currTree->nextNode[doubleMasked[i]];
    }
    bool inNH;
    
    if(subconfig->states[0] == -1){
        inNH = true;
        for(int i = 0; i < subconfig->childcons.size(); i++){
            if(!in_subconfig(nh,subconfig->childcons[i])){
                inNH = false;
                break;
            }
        }
        if(inNH){
            return true;
        }
    }
    else if(subconfig->num == 127){
        if(subconfig->childcons.size() != 0){
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < currTree->leaf.subTrs[i][henselmap[subconfig->hensel]].size(); j++){
                    inNH = true;
                    for(int k = 0; k < subconfig->childcons.size(); k++){
                        if(!in_subconfig(maskedNH,subconfig->childcons[k],currTree->leaf.subTrs[i][henselmap[subconfig->hensel]][j])){
                            inNH = false;
                            break;
                        }
                    }
                    if(inNH){
                        return true;
                    }
                }
            }
        }
        else{
            for(int i = 0; i < 9; i++){
                if(currTree->leaf.subTrs[i][henselmap[subconfig->hensel]].size() != 0){
                    return true;
                }
            }
        }
    }
    else if(subconfig->hensel == 127){
        if(subconfig->childcons.size() != 0){
            for(int i = 0; i < 13; i++){
                for(int j = 0; j < currTree->leaf.subTrs[subconfig->num][i].size(); j++){
                    inNH = true;
                    for(int k = 0; k < subconfig->childcons.size(); k++){
                        if(!in_subconfig(maskedNH,subconfig->childcons[k],currTree->leaf.subTrs[subconfig->num][i][j])){
                            inNH = false;
                            break;
                        }
                    }
                    if(inNH){
                        return true;
                    }
                }
            }
        }
        else{
            for(int i = 0; i < 13; i++){
                if(currTree->leaf.subTrs[subconfig->num][i].size() != 0){
                    return true;
                }
            }
        }
    }
    else{
        if(subconfig->childcons.size() != 0){
            for(int i = 0; i < currTree->leaf.subTrs[subconfig->num][henselmap[subconfig->hensel]].size(); i++){
                inNH = true;
                for(int j = 0; j < subconfig->childcons.size(); j++){
                    if(!in_subconfig(maskedNH,subconfig->childcons[j],currTree->leaf.subTrs[subconfig->num][henselmap[subconfig->hensel]][i])){
                        inNH = false;
                        break;
                    }
                }
                if(inNH){
                    return true;
                }
            }
        }
        else{
            if(currTree->leaf.subTrs[subconfig->num][henselmap[subconfig->hensel]].size() != 0){
                return true;
            }
        }
    }
    return false;
}

void rot(int * nh, int * target){
    /* 7 0 1    5 6 7
       6 8 2 -> 4 8 0
       5 4 3    3 2 1 */
    target[0] = nh[6];
    target[1] = nh[7];
    target[2] = nh[0];
    target[3] = nh[1];
    target[4] = nh[2];
    target[5] = nh[3];
    target[6] = nh[4];
    target[7] = nh[5];
    target[8] = nh[8];
}
void refl(int * nh, int * target){
    /* 7 0 1    1 0 7
       6 8 2 -> 2 8 6
       5 4 3    3 4 5 */
    target[0] = nh[0];
    target[1] = nh[7];
    target[2] = nh[6];
    target[3] = nh[5];
    target[4] = nh[4];
    target[5] = nh[3];
    target[6] = nh[2];
    target[7] = nh[1];
}

/* ---ANYTHING ABOVE THIS POINT SHOULD NOT BE CALLED OUTSIDE OF THIS FILE--- */

bool load_rule(std::string rs){
    if(tree.nextNode[0] == nullptr){
        set_up_tree();
    }
    if(!valid_rulestring(rs)){
        return false;
    }
    parse_rulestring(rs);
    if(!unique_states()){
        return false;
    }
    for(int i = 0;i < rule.size(); i++){
        for(int j = 0; j < rule[i].constraints.size(); j++){
            for(int k = 0; k < rule[i].constraints[j].subcfgs.size(); k++){
                delete rule[i].constraints[j].subcfgs[k];
            }
        }
        for(int j = 0; j < rule[i].negconstraints.size(); j++){
            for(int k = 0; k < rule[i].negconstraints[j].subcfgs.size(); k++){
                delete rule[i].negconstraints[j].subcfgs[k];
            }
        }
    }
    rule = newrule;
    if(ruletree != nullptr){
        delete ruletree;
        currLeaves = 0;
    }
    numStates = tempnumstates;
    ruletree = new RtNode(numStates);
    process_rule();
    process_rule_p2();
    return true;
}
int transition(int n, int ne, int e, int se, int s, int sw, int w, int nw, int center){
    int nh[8] = {n,ne,e,se,s,sw,w,nw};
    int nhc[9] = {n,ne,e,se,s,sw,w,nw,center};

    RtNode * currNode = ruletree;
    bool inRuletree = true;
    for(int i = 0; i < 9; i++){
        if(currNode->nextCell[nhc[i]] == nullptr){
            inRuletree = false;
            break;
        }
        currNode = currNode->nextCell[nhc[i]];
    }
    if(inRuletree){
        return currNode->endState;
    }

    std::vector<bool> negged(numStates+1,false);
    bool hasConstraint;
    for(int i = 0; i < rule[center].negconstraints.size(); i++){
        if(!negged[rule[center].negconstraints[i].endState]){
            hasConstraint = true;
            for(int j = 0; j < rule[center].negconstraints[i].sections.size(); j++){
                hasConstraint = has_subconstraint(nh,rule[center].negconstraints[i].sections[j]);
                if(!hasConstraint){
                    break;
                }
            }
            
            if(hasConstraint){
                for(int j = 0; j < rule[center].negconstraints[i].subcfgs.size(); j++){
                    hasConstraint = in_subconfig(nh,rule[center].negconstraints[i].subcfgs[j]);
                    if(!hasConstraint){
                        break;
                    }
                }
            }
            negged[rule[center].negconstraints[i].endState] = hasConstraint;
        }
    }
    int end = 0;
    for(int i = 0; i < rule[center].constraints.size(); i++){
        if(!negged[rule[center].constraints[i].endState]){
            hasConstraint = true;
            for(int j = 0; j < rule[center].constraints[i].sections.size(); j++){
                hasConstraint = has_subconstraint(nh,rule[center].constraints[i].sections[j]);
                if(!hasConstraint){
                    break;
                }
            }
            if(hasConstraint){
                for(int j = 0; j < rule[center].constraints[i].subcfgs.size(); j++){
                    hasConstraint = in_subconfig(nh,rule[center].constraints[i].subcfgs[j]);
                    if(!hasConstraint){
                        break;
                    }
                }
            }
            if(hasConstraint){
                end = rule[center].constraints[i].endState;
                break;
            }
        }
    }
    if(currLeaves < maxLeaves){
        int othernhc[9];
        bool newbranch;

        for(int x = 0; x < 8; x++){
            currNode = ruletree;
            newbranch = false;
            for(int i = 0; i < 9; i++){
                if(currNode->nextCell[nhc[i]] == nullptr){
                    currNode->nextCell[nhc[i]] = new RtNode(numStates);
                    newbranch = true;
                }
                currNode = currNode->nextCell[nhc[i]];
            }
            if(newbranch){
                currNode->endState = end;
                currLeaves++;
            }
            if(x == 3){
                refl(nhc,othernhc);
            }
            else{
                rot(nhc,othernhc);
            }
            for(int i = 0; i < 8; i++){
                nhc[i] = othernhc[i];
            }
        }
    }

    return end;
}


int main(){
    set_up_tree();

    //std::string rulestr = "B1.;3/S1.;2.;3/2T3.3;1+2:6c(1:2a;2:1c;3:2a;1+2:3i;2+3:3i;1+2+3:5a)/3T2-1;2;3(;1;)/4T2./5T2.-1;2;3";
    std::string rulestr = "B1.;3/S1.;3-;3a";

    //if(!load_rule(rulestr)){
        //throw "x";
    //}
    rulestr = "B1.;3/S1.;2.;3/2T3.(1:2a;2:1c;3:2a;1+2:3i;2+3:3i;1+2+3:5a)()/3T2-1;2;3(;1;)/4T2./5T2.1+2+3:3a-1;2;3/2T5.-1;2;3";
    if(!load_rule(rulestr)){
        throw "x";
    }
    int t = transition(1,2,3,3,0,0,0,1,2);
    int t2 = transition(0,1,1,2,2,2,3,3,2);


    return 0;
}