<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>

from typing import List
import bisect

class SegmentTree:
    def __init__(self, size):
        self.N = 1
        while self.N < size:
            self.N <<= 1
        self.size = self.N
        self.tree = [-1] * (2 * self.N)
    
    def update(self, index, value):
        index += self.N - 1
        if value > self.tree[index]:
            self.tree[index] = value
            index >>= 1
            while index >= 1:
                self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])
                index >>= 1
    
    def query(self, left, right):
        res = -1
        left += self.N - 1
        right += self.N - 1
        while left <= right:
            if left % 2 == 1:
                res = max(res, self.tree[left])
                left += 1
            if right % 2 == 0:
                res = max(res, self.tree[right])
                right -= 1
            left >>= 1
            right >>= 1
        return res

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums1)
        q = len(queries)
        
        # Step 1: Coordinate Compression for nums2 and yi
        unique_y = set(nums2)
        for query in queries:
            unique_y.add(query[1])
        sorted_unique_y = sorted(unique_y)
        y_to_idx = {y: i + 1 for i, y in enumerate(sorted_unique_y)}  # 1-based indexing
        
        # Step 2: Prepare points and sort them
        points = []
        for j in range(n):
            points.append((nums1[j], nums2[j], nums1[j] + nums2[j]))
        points.sort(reverse=True, key=lambda x: x[0])  # Sort by nums1[j] descending
        
        # Step 3: Prepare queries with their original indices and sort them
        queries_with_indices = []
        for i, (xi, yi) in enumerate(queries):
            queries_with_indices.append((xi, yi, i))
        queries_with_indices.sort(reverse=True, key=lambda x: x[0])  # Sort by xi descending
        
        # Step 4: Initialize Segment Tree
        st_size = len(sorted_unique_y)
        st = SegmentTree(st_size)
        
        # Step 5: Iterate through queries and points
        answer = [-1] * q
        j_ptr = 0
        for xi, yi, original_idx in queries_with_indices:
            # Add all points with nums1[j] >= xi
            while j_ptr < n and points[j_ptr][0] >= xi:
                y_j = points[j_ptr][1]
                sum_j = points[j_ptr][2]
                compressed_y = y_to_idx[y_j]
                st.update(compressed_y, sum_j)
                j_ptr += 1
            
            # Query the maximum sum_j where nums2[j] >= yi
            # Find the smallest y >= yi
            idx = bisect.bisect_left(sorted_unique_y, yi) + 1  # 1-based indexing
            if idx > st_size:
                answer[original_idx] = -1
            else:
                max_sum = st.query(idx, st_size)
                answer[original_idx] = max_sum if max_sum != -1 else -1
        
        return answer

69200