class Node{
public:
    bool terminal;
    std::map<char, Node*> map;
public:
    Node(bool t){
        terminal = t;
    }
};

class Tries{
public:
    Node* root;
public:
    Tries(){
        root = new Node(true);
    }
};

void insert(Node* root, std::string str, int i){
    if(i < str.size()){
        if(i == str.size() - 1){
            if(root->map[str[i]] != NULL)
                root->map[str[i]]->terminal = true;
            else
                root->map[str[i]] = new Node(true);
        }else{
            if(root->map[str[i]] == NULL)
                root->map[str[i]] = new Node(false);
            
            insert(root->map[str[i]], str, i+1);
        }
    }
}

bool contain(Node* root, std::string str, int i){
    if(root){
        if(str.size() == 0)
            return root->terminal;
        
        if(i == str.size() - 1){
            if(root->map[str[i]] != NULL)
                return root->map[str[i]]->terminal;
            else
                return false;
        }else{
            return contain(root->map[str[i]], str, i+1);
        }
    }else{
       return false;
    }
}