Imagine you are the manager of a rental storage facility with N units. The units are represented by a 2D integer array of units where $units[i] = [unitId_i, size_i]$ denotes that there is a unit with a unit number $unitId_i$ and size equal to $size_i$. Each $unitId_i$ is guaranteed to be unique.

Your customers have made $K$ requests in a 2D array requests where $requests[j] = [preferred_j, minSize_j]$. The answer to the $j^{th}$ request is the unit number id of a unit such that:

The unit has a size of at least $minSize_j$, and $abs(id – preferred_j)$ is minimized, where abs(x) is the absolute value of x. If there is no such unit, the answer is -1

Return an array $answer$ of length $K$ where $answer[j]$ contains the answer to the $j^{th}$ request.

Note: If there is a tie in the absolute difference, then use the unit with the smallest such ID.

Example 1

Assumptions

Input

• N = 3
• units = [[2, 2], [1, 2], [3, 2]]
• K = 3
•  requests = [[3, 1], [3, 3], [5, 2]]

Output: 3 -1 3

Approach

First, unit number 3 is the closest as its size >=1 and abs(3-3)=0.

Second, no unit has a size greater or equal to 3.

Third, unit number 3 is the closest as its size >=2 and abs(5-3)=2.

Function description

Complete the function solve() provided in the editor. The function takes the following 4 parameters and returns the solution:

• N: Represents the number of units
• units: Represents the description of units
• K: Represents the number of requests
• requests: Represents the description of requests

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don’t provide boilerplate code

• The first line contains N denoting the number of units.
• Each of the next N lines contains the description of the i^th unit.
• The next line contains K denoting the number of requests.
• Each of the next K lines contains the description of the j^th request.

Output format

Print an array, representing the result to each query.

Constraints

$1 \le N \le 10^5 \\ 1 \le K \le 10^4 \\ 1 \le units[i][0], units[i][1], requests[j][0], requests[j][1] \le 10^7$