<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
from bisect import bisect_left

class SegmentTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [-1] * (4 * n)
    
    def update(self, ind: int, val: int):
        self._update(ind, val, 0, self.n - 1, 0)
    
    def _update(self, ind: int, val: int, l: int, r: int, i: int):
        if l == r:
            self.tree[i] = val
            return
        
        m = (l + r) >> 1
        if m >= ind:
            self._update(ind, val, l, m, i * 2 + 1)
        else:
            self._update(ind, val, m + 1, r, i * 2 + 2)
        
        self.tree[i] = max(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    
    def query(self, x: int, y: int) -> int:
        return self._query(x, y, 0, self.n - 1, 0)
    
    def _query(self, x: int, y: int, l: int, r: int, i: int) -> int:
        if r < x or l > y:
            return -1
        if l >= x and r <= y:
            return self.tree[i]
        
        m = (l + r) >> 1
        return max(
            self._query(x, y, l, m, i * 2 + 1),
            self._query(x, y, m + 1, r, i * 2 + 2)
        )

class Node:
    def __init__(self, ind: int, val: int, sum_: int):
        self.val = val
        self.ind = ind
        self.sum = sum_
    
    def __lt__(self, other):
        return self.val > other.val

class Query:
    def __init__(self, num1: int, num2: int, ind: int):
        self.num1 = num1
        self.num2 = num2
        self.ind = ind
    
    def __lt__(self, other):
        return self.num2 > other.num2

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:

        # THIS IS SEGMENT TREE SOLUTION ( THERE IS SOL'n using MAP )
        # Try that out when u visit next time

        # Here we also use Monotonic stack to override the points 
        # from the lower points as those are not considered at all

        # The Below Code is using ( Activation Technique ) by coding mohan
        # Also there a approach by VIVEK GUPTA which is Beautiful 
        # JUST figuring the out line which will cover the other points
        # Even that uses ( SEGMENT TREE ) but it it Good

        n = len(nums1)
        tree = SegmentTree(n)
        
        num1_and_ind = []
        num2_ind_and_sum = []
        
        for j in range(n):
            num1_and_ind.append((nums1[j], j))
        num1_and_ind.sort()
        
        for j in range(n):
            ind = num1_and_ind[j][1]
            num2_ind_and_sum.append(Node(j, nums2[ind], nums1[ind] + nums2[ind]))
        num2_ind_and_sum.sort()
        
        query_list = []
        for j in range(len(queries)):
            query_list.append(Query(queries[j][0], queries[j][1], j))
        query_list.sort()
        
        result = [0] * len(queries)
        inactive_ind = 0
        
        for q in query_list:
            while inactive_ind < n and num2_ind_and_sum[inactive_ind].val >= q.num2:
                node = num2_ind_and_sum[inactive_ind]
                tree.update(node.ind, node.sum)
                inactive_ind += 1
            
            l = bisect_left(num1_and_ind, (q.num1, -1))
            r = n - 1
            
            result[q.ind] = tree.query(l, r) if l <= r else -1
        
        return result

        
81600