Scalable approach w/ efficient Binary Search + Sparse Table (RMQ)
Code\n\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        yx = list(zip(nums
# Code\n```\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        yx = list(zip(nums2, nums1))\n        xsum = [(x, x + y) for y, x in yx]\n        xsum.sort()\n        xs = [x for x, _ in xsum]\n        sums = [s for _, s in xsum]\n\n        def RMQ(sums):\n            n = len(sums)\n            k = n.bit_length() + 1\n            st = [[None for _ in range(n)] for _ in range(k)]\n\n            for i in range(n):\n                st[0][i] = sums[i]\n\n            for p in range(1, k):\n                for i in range(n):\n                    nxt = i + (1 << (p - 1))\n                    if nxt < n:\n                        st[p][i] = max(st[p - 1][i], st[p - 1][nxt])\n                    else:\n                        st[p][i] = st[p - 1][i]\n\n            def query(l, r):\n                p = (r - l + 1).bit_length() - 1\n                len_ = 1 << p\n                return max(st[p][l], st[p][r - len_ + 1])\n\n            return query\n\n        rmq = RMQ(sums)\n\n        yx.sort()\n        ys = [y for y, _ in yx]\n        sufmaxxs = list(reversed(list(accumulate([x for y, x in reversed(yx)], max))))\n\n        ans = []\n        for xq, yq in queries:\n            indxy = bisect.bisect_left(ys, yq)\n\n            if indxy == len(ys):\n                ans.append(-1)\n                continue\n            maxx = sufmaxxs[indxy]\n            if maxx < xq:\n                ans.append(-1)\n                continue\n            rindxx = bisect.bisect_right(xs, maxx) - 1\n            lindxx = bisect.bisect_left(xs, xq)\n            if lindxx == len(xs):\n                ans.append(-1)\n                continue\n            ans.append(rmq(lindxx, rindxx))\n\n        return ans\n\n\n```
['Python3']