Note the unusual memory limit.
Adamant is a famous person for writing educational blog posts on math and programming. One day, he finally decides that he has written too many blogs and it's time to go outside and touch some grass.
Adamant has a lawn on which $$$n$$$ grass plants grow. The grasses are indexed from $$$1$$$ to $$$n$$$. We can draw the lawn and grasses on the 2D plane: the ground is the line $$$y=0$$$, and grasses grow up vertically. Each grass can be described by two numbers $$$x$$$ and $$$y$$$, meaning it can be considered as a vertical line segment from $$$(x, 0)$$$ to $$$(x, y)$$$.
To touch grass, Adamant will move his hand $$$m$$$ times. Each time he moves his hand from the coordinates $$$(x_1, y_1)$$$ to the coordinates $$$(x_2, y_2)$$$ along a straight path. We say that his hand touches the $$$i$$$-th grass, if the segment $$$(x_1, y_1) - (x_2, y_2)$$$ touches the segment (or its endpoints) defined by the $$$i$$$-th grass.
Your task is to determine, for each time Adamant moves his hand, whether he will touch any grass. If the answer is yes, you also need to find the index of any grass he will touch.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 8 \times 10^5$$$).
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x, y$$$ ($$$1 \le x, y \le 10^9$$$) describing the grass with index $$$i$$$. It is guaranteed that no two grasses have the same $$$x$$$.
The next line contains an integer $$$m$$$ ($$$1 \le m \le 3 \times 10^5$$$).
Each of the next $$$m$$$ lines contains four integers $$$x_1, y_1, x_2, y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le 10^9$$$) describing a hand movement. It is guaranteed that both $$$x_1$$$ and $$$x_2$$$ are different from the $$$x$$$-coordinate of any grass.
For each hand movement, print one line: the index of any grass that is touched. If there are multiple answers, print any one of them. If no grass is touched, print $$$-1$$$.
32 36 44 531 4 7 67 4 1 21 6 1 6
3 1 -1
Visualization of the sample:
