python3 sorted list template
\n\nfrom bisect import bisect_left as lower_bound\nfrom bisect import bisect_right as upper_bound\n\n\nclass FenwickTree:\n    def __init__(self, x):\n        b
\n```\nfrom bisect import bisect_left as lower_bound\nfrom bisect import bisect_right as upper_bound\n\n\nclass FenwickTree:\n    def __init__(self, x):\n        bit = self.bit = list(x)\n        size = self.size = len(bit)\n        for i in range(size):\n            j = i | (i + 1)\n            if j < size:\n                bit[j] += bit[i]\n\n    def update(self, idx, x):\n        """updates bit[idx] += x"""\n        while idx < self.size:\n            self.bit[idx] += x\n            idx |= idx + 1\n\n    def __call__(self, end):\n        """calc sum(bit[:end])"""\n        x = 0\n        while end:\n            x += self.bit[end - 1]\n            end &= end - 1\n        return x\n\n    def find_kth(self, k):\n        """Find largest idx such that sum(bit[:idx]) <= k"""\n        idx = -1\n        for d in reversed(range(self.size.bit_length())):\n            right_idx = idx + (1 << d)\n            if right_idx < self.size and self.bit[right_idx] <= k:\n                idx = right_idx\n                k -= self.bit[idx]\n        return idx + 1, k\n\n\nclass SortedList:\n    block_size = 700\n\n    def __init__(self, iterable=()):\n        self.macro = []\n        self.micros = [[]]\n        self.micro_size = [0]\n        self.fenwick = FenwickTree([0])\n        self.size = 0\n        for item in iterable:\n            self.insert(item)\n\n    def insert(self, x):\n        i = lower_bound(self.macro, x)\n        j = upper_bound(self.micros[i], x)\n        self.micros[i].insert(j, x)\n        self.size += 1\n        self.micro_size[i] += 1\n        self.fenwick.update(i, 1)\n        if len(self.micros[i]) >= self.block_size:\n            self.micros[i:i + 1] = self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:]\n            self.micro_size[i:i + 1] = self.block_size >> 1, self.block_size >> 1\n            self.fenwick = FenwickTree(self.micro_size)\n            self.macro.insert(i, self.micros[i + 1][0])\n\n    def pop(self, k=-1):\n        i, j = self._find_kth(k)\n        self.size -= 1\n        self.micro_size[i] -= 1\n        self.fenwick.update(i, -1)\n        return self.micros[i].pop(j)\n\n    def __getitem__(self, k):\n        i, j = self._find_kth(k)\n        return self.micros[i][j]\n\n    def count(self, x):\n        return self.upper_bound(x) - self.lower_bound(x)\n\n    def __contains__(self, x):\n        return self.count(x) > 0\n\n    def lower_bound(self, x):\n        i = lower_bound(self.macro, x)\n        return self.fenwick(i) + lower_bound(self.micros[i], x)\n\n    def upper_bound(self, x):\n        i = upper_bound(self.macro, x)\n        return self.fenwick(i) + upper_bound(self.micros[i], x)\n\n    def _find_kth(self, k):\n        return self.fenwick.find_kth(k + self.size if k < 0 else k)\n\n    def __len__(self):\n        return self.size\n\n    def __iter__(self):\n        return (x for micro in self.micros for x in micro)\n\n    def __repr__(self):\n        return str(list(self))\n\n\n\nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n        d = defaultdict(int)\n        que = sorted(queries,key = lambda a : a[1] , reverse = True)\n        rooms.sort(key = lambda a : a[1] , reverse = True)\n        s = SortedList()\n        i = 0\n        for a,b in que:\n            while i<len(rooms) and rooms[i][1] >= b:\n                s.insert(rooms[i][0])\n                i+=1\n            if not len(s):\n                d[(a,b)] = -1\n            else:\n                ans = inf\n                r = -1\n                id = s.lower_bound(a)\n                if 0<=id-1<len(s):\n                    if abs(s[id-1]-a) < ans:\n                        ans = abs(s[id-1]-a)\n                        r = s[id-1]\n                if 0<=id<len(s):\n                    if abs(s[id]-a) < ans:\n                        ans = abs(s[id]-a)\n                        r = s[id]\n                d[(a,b)] = r\n        res = []\n        for a,b in queries:\n            res.append(d[(a,b)])\n        return res\n```
['Python3']