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

    def get_right(self, value):
        return (value >> 32) & self.MASK

    @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])
        if left_node:
            self._remove_nodes(left_node)
        right_node = self.get_right(self.nodes[node])
        if right_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

        self.nodes[current_node] |= 1
        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)

    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


def get_data(address):
    if '/' in address:
        address, routing_prefix = address.split('/')
        size = 32 - int(routing_prefix)
    else:
        size = 0

    address = list(map(int, address.split('.')))

    value = 0
    for item in address:
        value <<= 8
        value ^= item

    value >>= size
    value <<= size
    return value, 32 - size


arr = ['132.43.43.4', '132.132.123.123/16', '12.3.3.3', '123.123.132.123']
brr = ['9.9.9.9', '123.123.123.123/1', '12.3.3.4', '123.0.0.0', '0.0.0.0', '312.32.32.32/13']

binaryTrie = BinaryTrie()

for address in arr:
    value, size = get_data(address)
    binaryTrie.add_address(value, size)

arr += brr
for address in arr:
    value, size = get_data(address)
    print(binaryTrie.__contains__(value, size))

print(binaryTrie.__sizeof__())