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



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

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

    @staticmethod
    def get_right(value):
        return value >> 32

    @staticmethod
    def get_type(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_address(self, value, size):
        current_node = 0
        for i in range(size):
            bit = 31 - i
            if self.get_type(self.nodes[current_node]) == 1:
                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 << 32
                current_node = current_right

        current_left = self.get_left(self.nodes[current_node])
        current_right = self.get_right(self.nodes[current_node])

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

        self.nodes[current_node] = 1

    def __contains__(self, value, size):
        current_node = 0
        for i in range(size):
            bit = 31 - i
            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