Limits
2s, 512 MB

Gondor has $n$ circular gold mines with IDs from $1$ to $n$ containing some gold. Each mine’s center can be located by a 2D coordinate.

Ri, the miner, lives in a place in Gondor that a coordinate on a 2D plane can locate. She can dig mines that only cover her place. In other words, she can dig a mine if her location lies inside or on the boundary of that mine.

Even though it would have been better to dig all the mines, she unable to move much for sickness and can only dig one mine at most. So, she wants to dig the mine that contains the most amount of gold. Help her to find the most suitable one.

The first line of the input will consist of an integer $t\ ( 1\le t\le 10^5)$$-$ the number of testcases. The description of each testcase follows:

The first line of the testcase will consist of an integer $n\ ( 1\le n\le 3\cdot10^5)$ $-$ the number of gold mines.

Next $n$ lines will contain four integers, $M_{x_i},\ M_{y_i},\ r_i,\ a_i$$(-10^9\le M_{x_i}, M_{y_i}\le 10^9,$$\ 1\le r_i,\ a_i\le 10^9)$$-$ the coordinates of the center of the mines, the radius of the mines, and amount of gold in each mine respectively.

Next line will contain an integer $q\ (1 \le q \le 3\cdot10^5)$$-$ number of queries.

Each query will contain two integers in a line, $x_i, y_i\ ( -10^9\le x_i, y_i\le 10^9)$$-$ coordinates of Ri’s location.

Additional constraints for the queries: Either $x_i - x_{j} = 0$ or $y_i - y_{j} = 0$ or both for all $1\le i < j\le q$.

Moreover, you can assume that the sum of $n$ and the sum of $q$ over all testcases will not exceed $3\cdot10^5$ respectively.

For each query, print the ID of the mine that Ri will dig. If there are multiple mines, print the minimum ID. If no mines cover Ri’s place, print $-1$.

Input | Output |
---|---|

1 3 0 0 1 3 -1 0 1 10 -1 -1 2 9 3 -1 -2 -1 1 -1 2 | 3 2 -1 |

See the image to understand the sample case. Here, the $\textcolor{blue}{blue}$ dots are the center of the circles and the $\textcolor{red}{red}$ dots are the places of Ri. |

Login to submit.

63%
Solution Ratio

Nafis2003174.132453Earliest,

YouKnowWhoFastest, 0.4s

dlwlrm4Lightest, 23 MB

NadiimShortest, 1794B

Toph uses cookies. By continuing you agree to our Cookie Policy.