Online Binary search + RMQ(sparse tables), detailed explanation
Intuition\nFirst we sort the points by $y$. Denote the sorted array $P_y$. Also we will need $P_x$, array with points sorted by $x$ coordinate.\n\nThen for each
# Intuition\nFirst we sort the points by $y$. Denote the sorted array $P_y$. Also we will need $P_x$, array with points sorted by $x$ coordinate.\n\nThen for each query $q = (x_q, y_q)$:\n\n1. We find the point with the largest $x$ among the ones with $y \\geq y_q$. Denote the $x$ coordinate of this point $x_r$. For query $q$ we use binary search to get the index of the first point with $y \\geq y_q$ in $P_y$, and then we use precomputed *suffix maximums* array of $x$ coordinates over $P$. Note that $P_y$ is sorted by $y$, but maximums are computed over $x$!\n2. We find the point with the least coordinate $x$ s.t. $x \\geq x_q$. This is done using binary search over $P_x$. Denote this coordinate $x_l$.\n3. We perform RMQ over all points with $x_l \\leq x \\leq x_r$. We search for the maximum $x + y$. This is achieved via precomputed array of $x + y$, ordered according to $P_x$. The actual RMQ is done using Sparse Table.\n\n# Why does it work?\nThe answer for each query is $\\max\\limits_{x_l \\leq x_i \\leq x_r} x_i + y_i$. Recall that $x_l = \\min\\limits_{x_i \\geq x_q} x_i$ and $x_r = \\max\\limits_{y_i \\geq y_q} x_i$. This way we have unwanted extra points: the ones with $y < y_q$. But notice that they are guaranteed to be suboptimal: we already have a point with $x = x_r$ and $y \\geq y_q$, while each extra point has $x \\leq x_r$ and $y \\leq y_q$! So our maximum, in fact, gives the desired answer.\n\n# Complexity\n- Time complexity:\n    - Precomputation: $O(n \\log n)$ for several array sorts and sparse table precomputation\n    - Queries: $O(q \\log n)$, as for each query we do a couple of binary searches for $O(\\log n)$ each and one RMQ query, which is $O(1)$\n    - Total: $O((n + q) \\log n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n \\log n)$ for sparse table \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass RMQ:\n    def __init__(self, arr):\n        self.arr = arr\n        self.n = len(arr)\n        self.k = self.n.bit_length() + 1\n        self.st = [[None for _ in range(self.n)] for _ in range(self.k)]\n\n        for i in range(self.n):\n            self.st[0][i] = self.arr[i]\n        \n        for p in range(1, self.k):\n            for i in range(self.n):\n                nxt = i + (1 << (p - 1))\n                if nxt < self.n:\n                    self.st[p][i] = max(self.st[p - 1][i], self.st[p - 1][nxt])\n                else:\n                    self.st[p][i] = self.st[p - 1][i]\n    def query(self, l, r):\n        p = (r - l + 1).bit_length() - 1\n        len_ = 1 << p\n        return max(self.st[p][l], self.st[p][r - len_ + 1])\n\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n\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        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)],\n                                             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.query(lindxx, rindxx))\n        \n        return ans\n```
['Binary Search', 'Python3']