<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums1</code> and <code>nums2</code>, each of length <code>n</code>, and a <strong>1-indexed 2D array</strong> <code>queries</code> where <code>queries[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>For the <code>i<sup>th</sup></code> query, find the <strong>maximum value</strong> of <code>nums1[j] + nums2[j]</code> among all indices <code>j</code> <code>(0 &lt;= j &lt; n)</code>, where <code>nums1[j] &gt;= x<sub>i</sub></code> and <code>nums2[j] &gt;= y<sub>i</sub></code>, or <strong>-1</strong> if there is no <code>j</code> satisfying the constraints.</p>

<p>Return <em>an array </em><code>answer</code><em> where </em><code>answer[i]</code><em> is the answer to the </em><code>i<sup>th</sup></code><em> query.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
<strong>Output:</strong> [6,10,7]
<strong>Explanation:</strong> 
For the 1st query <code node="[object Object]">x<sub>i</sub> = 4</code>&nbsp;and&nbsp;<code node="[object Object]">y<sub>i</sub> = 1</code>, we can select index&nbsp;<code node="[object Object]">j = 0</code>&nbsp;since&nbsp;<code node="[object Object]">nums1[j] &gt;= 4</code>&nbsp;and&nbsp;<code node="[object Object]">nums2[j] &gt;= 1</code>. The sum&nbsp;<code node="[object Object]">nums1[j] + nums2[j]</code>&nbsp;is 6, and we can show that 6 is the maximum we can obtain.

For the 2nd query <code node="[object Object]">x<sub>i</sub> = 1</code>&nbsp;and&nbsp;<code node="[object Object]">y<sub>i</sub> = 3</code>, we can select index&nbsp;<code node="[object Object]">j = 2</code>&nbsp;since&nbsp;<code node="[object Object]">nums1[j] &gt;= 1</code>&nbsp;and&nbsp;<code node="[object Object]">nums2[j] &gt;= 3</code>. The sum&nbsp;<code node="[object Object]">nums1[j] + nums2[j]</code>&nbsp;is 10, and we can show that 10 is the maximum we can obtain. 

For the 3rd query <code node="[object Object]">x<sub>i</sub> = 2</code>&nbsp;and&nbsp;<code node="[object Object]">y<sub>i</sub> = 5</code>, we can select index&nbsp;<code node="[object Object]">j = 3</code>&nbsp;since&nbsp;<code node="[object Object]">nums1[j] &gt;= 2</code>&nbsp;and&nbsp;<code node="[object Object]">nums2[j] &gt;= 5</code>. The sum&nbsp;<code node="[object Object]">nums1[j] + nums2[j]</code>&nbsp;is 7, and we can show that 7 is the maximum we can obtain.

Therefore, we return&nbsp;<code node="[object Object]">[6,10,7]</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
<strong>Output:</strong> [9,9,9]
<strong>Explanation:</strong> For this example, we can use index&nbsp;<code node="[object Object]">j = 2</code>&nbsp;for all the queries since it satisfies the constraints for each query.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
<strong>Output:</strong> [-1]
<strong>Explanation:</strong> There is one query in this example with <code node="[object Object]">x<sub>i</sub></code> = 3 and <code node="[object Object]">y<sub>i</sub></code> = 3. For every index, j, either nums1[j] &lt; <code node="[object Object]">x<sub>i</sub></code> or nums2[j] &lt; <code node="[object Object]">y<sub>i</sub></code>. Hence, there is no solution. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>nums1.length == nums2.length</code>&nbsp;</li>
	<li><code>n ==&nbsp;nums1.length&nbsp;</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup>&nbsp;</code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length ==&nbsp;2</code></li>
	<li><code>x<sub>i</sub>&nbsp;== queries[i][1]</code></li>
	<li><code>y<sub>i</sub> == queries[i][2]</code></li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
</ul>

class TreeNode:
    def __init__(self, start, end, val, left, right):
        self.start = start
        self.end = end
        self.val = val
        self.left = left
        self.right = right
class SegmentTree:
    def __init__(self, N):
        def build(start, end):
            if start == end:
                return TreeNode(start, end, -1, None, None)
            mid = start + (end - start) // 2
            left = build(start, mid)
            right = build(mid+1, end)
            return TreeNode(start, end, -1, left, right)
        self.root = build(0, N-1)
    def update(self, i, val):
        def doUpdate(node, i, val):
            if node.start == i and node.end == i:
                node.val = val
                return
            mid = node.start + (node.end - node.start) // 2
            if i <= mid:
                doUpdate(node.left, i, val)
            else:
                doUpdate(node.right, i, val)
            node.val = max(node.left.val, node.right.val)
        doUpdate(self.root, i, val)
    def query(self, start, end):
        def doQuery(node, start, end):
            if node.start == start and node.end == end:
                return node.val
            mid = node.start + (node.end - node.start) // 2
            if mid >= end:
                return doQuery(node.left, start, end)
            elif mid < start:
                return doQuery(node.right, start, end)
            return max(doQuery(node.left, start, mid), doQuery(node.right, mid+1, end))
        return doQuery(self.root, start, end)
class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        N = len(nums1)
        y_sorted_idx = [i for i in range(N)]
        y_sorted_idx.sort(key=lambda x:(nums2[x]))
        lookup = [-1 for _ in range(N)] # old index --> sorted pos
        for i in range(N):
            lookup[y_sorted_idx[i]] = i

        pair_sorted_by_x = [i for i in range(N)]
        pair_sorted_by_x.sort(key=lambda x:(nums1[x]))
        pair_sorted_by_x.reverse()
        M = len(queries)
        query_sorted_by_x = [i for i in range(M)]
        query_sorted_by_x.sort(key=lambda x:(queries[x][0]))
        query_sorted_by_x.reverse()

        i, j = 0, 0
        tree = SegmentTree(N)
        res = [-1 for _ in range(M)]
        while j < M:
            while i < N and nums1[pair_sorted_by_x[i]] >= queries[query_sorted_by_x[j]][0]:
                pos = pair_sorted_by_x[i]
                tree.update(lookup[pos], nums1[pos] + nums2[pos])
                i += 1

            target = queries[query_sorted_by_x[j]][1]
            left, right = 0, N-1
            while left < right:
                mid = left + (right - left) // 2
                if nums2[y_sorted_idx[mid]] >= target:
                    right = mid
                else:
                    left = mid + 1

            if nums2[y_sorted_idx[left]] < target:
                left += 1

            if left < N:
                res[query_sorted_by_x[j]] = tree.query(left, N-1)

            j += 1
        return res

84200