class RegionTree:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        self.child_regions = []
        self.values = []
    def add_item(self, range_obj, value):
        if self.left == range_obj.start and self.right == range_obj.stop:
            self.values.append(value)
        else:
            middle = int((self.left + self.right) / 2)
            if not self.child_regions:
                self.child_regions = [RegionTree(self.left, middle), RegionTree(middle, self.right)]
            if range_obj.stop <= middle:
                #exists only in left region
                self.child_regions[0].add_item(range_obj, value)
            elif range_obj.start >= middle:
                #exists only in right region
                self.child_regions[1].add_item(range_obj, value)
            else:
                #exists in both regions
                left_range = range(range_obj.start, middle)
                right_range = range(middle, range_obj.stop)
                self.child_regions[0].add_item(left_range, value)
                self.child_regions[1].add_item(right_range, value)
    def in_range(self, key):
        return self.left <= key < self.right
    def get_items(self, key):
        assert self.in_range(key)
        for val in self.values:
            yield val
        for child_region in self.child_regions:
            if child_region.in_range(key):
                yield from child_region.get_items(key)
    def get_first_item(self, key):
        return next(self.get_items(key))

x = RegionTree(-500, 500)
x.add_item(range(0,6), 0)
x.add_item(range(6, 10), 1)
print(x.get_first_item(0))
print(x.get_first_item(6))
print(x.get_first_item(9))