class BinaryTrie(object):
    def __init__(self, length):
        self.LENGTH = length + 1
        self.MASK = (1 << self.LENGTH) - 1
        self.nodes = [0 for _ in range(64)]
        self.empty_nodes = [63 - i for i in range(63)]

    def __sizeof__(self):
        return self.nodes.__sizeof__() + self.empty_nodes.__sizeof__()

    def __repr__(self):
        repr = []
        for i in range(len(self.nodes)):
            if i in self.empty_nodes:
                continue

            value = self.nodes[i]

            is_leaf = self._get_type(value) == 1
            left = self._get_left(value) or '-'
            right = self._get_right(value) or '-'

            if is_leaf:
                repr.append('%s:leaf' % (i,))
            else:
                repr.append('%s:%s/%s' % (i, left, right))

        return ' '.join(repr)

    def _get_left(self, value):
        return (value >> 1) & self.MASK

    def _get_right(self, value):
        return value >> (self.LENGTH + 1)

    def _get_type(self, value):
        return value & 1

    def _create_node(self):
        if len(self.empty_nodes) == 0:
            self.empty_nodes = [2 * len(self.nodes) - 1 - i for i in range(len(self.nodes))]
            self.nodes += [0 for _ in range(len(self.nodes))]
        index = self.empty_nodes.pop()
        return index


    def _remove_nodes(self, node):
        if node == 0:
            return

        self.empty_nodes.append(node)

        left_node = self._get_left(self.nodes[node])
        self._remove_nodes(left_node)

        right_node = self._get_right(self.nodes[node])
        self._remove_nodes(right_node)

        self.nodes[node] = 0

    def add(self, value, size=None):
        if size is None:
            size = self.LENGTH

        current_node = 0
        for i in range(size):
            bit = size - i - 1
            if self._get_type(self.nodes[current_node]) == 1: # leaf
                print(current_node, '!')
                return
            if (value >> bit) & 1 == 0:
                current_left = self._get_left(self.nodes[current_node])
                if current_left == 0:
                    current_left = self._create_node()
                    self.nodes[current_node] |= current_left << 1
                current_node = current_left
            else:
                current_right = self._get_right(self.nodes[current_node])
                if current_right == 0:
                    current_right = self._create_node()
                    self.nodes[current_node] |= current_right << (self.LENGTH + 1)
                current_node = current_right

        current_left = self._get_left(self.nodes[current_node]) #delete children if a vertex added
        current_right = self._get_right(self.nodes[current_node])

        self._remove_nodes(current_left)
        self._remove_nodes(current_right)

        self.nodes[current_node] = 1 #leaf

    def __contains__(self, value, size=None):
        if size is None:
            size = self.LENGTH

        current_node = 0
        for i in range(size):
            bit = size - i - 1
            if self._get_type(self.nodes[current_node]) == 1:
                return True
            if (value >> bit) & 1 == 0:
                current_left = self._get_left(self.nodes[current_node])
                if current_left == 0:
                    return False
                current_node = current_left
            else:
                current_right = self._get_right(self.nodes[current_node])
                if current_right == 0:
                    return False
                current_node = current_right
        return self._get_type(self.nodes[current_node]) == 1