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