Radix

def longest_common_base(x: str, y: str) -> str:
    if not x or not y:
        return ""
    i = 0
    while i < len(x) and i < len(y):
        if x[i] != y[i]:
            return x[:i]
        i += 1
    return x[:i]


def one_prefixes_other(x: str, y: str) -> bool:
    if not x or not y:
        return True
    return first_prefixes_second(x, y) or first_prefixes_second(y, x)

def first_prefixes_second(x: str, y: str) -> bool:
    if not x:
        return True
    if not y:
        return False
    if len(y) < len(x):
        return False
    return y[:len(x)] == x

class Node:
    def __init__(self, value: str = "", leaf: bool = True):
        if not isinstance(value, str):
            raise "wrong value type"
        self.value = value
        self.leaf = leaf
        self.children = {}
        self.size = 0

    def is_node(self) -> bool:
        return not self.leaf

    def insert_leaf_node_without_checking(self, new_node):
        if self.leaf:
            raise "cannot insert into a leaf"
        self.children[new_node.value] = new_node

    def contains_leaf(self, s: str) -> bool:
        if s in self.children:
            n: Node = self.children[s]
            return n.leaf
        for child_string in self.children:
            if first_prefixes_second(child_string, s):
                sub = s[len(child_string):]
                n: Node = self.children[child_string]
                return n.contains_leaf(sub)
        return False

    def insert_and_check(self, new_string: str) -> bool:
        # return true if one word is found to be a prefix of another.
        if self.leaf:
            raise "cannot insert into a leaf"
        common_base = ""
        for child_string in self.children:
            if first_prefixes_second(new_string, child_string):
                return True
            child_node = self.children[child_string]
            if child_node.is_node():
                if first_prefixes_second(child_string, new_string):
                    # This does not mean there is a dupicate, because it is a node.
                    sub = new_string[len(child_string):]
                    return child_node.insert_and_check(sub)
            else:
                # it is a leaf.  Check if this leaf is a prefix of the new value
                if first_prefixes_second(child_string, new_string):
                    return True
            b = longest_common_base(child_string, new_string)
            if len(b) > len(common_base):
                common_base = b
        if len(common_base) > 0:
            new_child = Node(common_base, leaf=False)
            to_del = []
            for child_string in self.children:
                node: Node = self.children[child_string]
                if node.is_node():
                    continue
                if first_prefixes_second(common_base, child_string):
                    to_del.append(child_string)
                    node.value = node.value[len(common_base):]
                    new_child.insert_leaf_node_without_checking(node)
            
            # don't forget to still insert the word that just arrived.
            sub = new_string[len(common_base):]
            new_child.insert_leaf_node_without_checking(Node(sub, leaf=True))

            for s in to_del:
                del self.children[s]
            self.children[common_base] = new_child
        else:
            self.children[new_string] = Node(new_string, leaf=True)
        self.size += 1
        return False



class Radix:
    def __init__(self):
        self.head = Node(value = "", leaf = False)

    def insert_and_check(self, v: str) -> bool:
        # return true if one word is found to be a prefix of another.
        return self.head.insert_and_check(v)

    def size(self) -> int:
        return self.head.size

    def contains_leaf(self, s: str) -> bool:
        return self.head.contains_leaf(s)