Meteorites

The Naro Space Center (NSC) has observed $k$ meteorites falling toward our city. The center wants to know which buildings the meteorites will hit.

Consider the two dimensional version of the problem first. The city has $n$ buildings. Every building is a rectangle whose bottom side lies on the $x$ axis, and no two rectangles overlap, so two distinct rectangles never meet. The rectangles are numbered from 1 to $n$, and rectangle 1 is the leftmost one. If $1 \le i < j \le n$, then rectangle $i$ lies to the left of rectangle $j$.

Every meteorite is a point. Each one falls along a slope given by a pair of integers $(dx, dy)$. A meteorite currently at $(x, y)$ with slope $(dx, dy)$ falls downward along the line through $(x, y)$ and $(x + dx, y + dy)$. In the figure above, meteorite A and meteorite B both head for building 3. When a meteorite touches any point on the boundary of a building, it explodes on the spot and disappears.

Given $n$ buildings and $k$ meteorites, write a program that reports which building each meteorite damages.

Your program reads from standard input. The first line holds an integer $n$ ($1 \le n \le 100000$), the number of rectangles that represent the buildings of the city. Each of the next $n$ lines holds one rectangle in left to right order, and the rectangles are numbered from 1 to $n$ in that order. Each rectangle is given by three integers $x_1$, $x_2$, and $h$ ($1 \le x_1 < x_2 \le 10^9$, $1 \le h < 10^9$), where $x_1$ is the $x$ coordinate of the left side, $x_2$ is the $x$ coordinate of the right side, and $h$ is the $y$ coordinate of the top side. The bottom side of every rectangle lies on the $x$ axis, and rectangle $i$ lies to the left of rectangle $j$ whenever $1 \le i < j \le n$. The next line holds an integer $k$ ($1 \le k \le 100000$), the number of meteorites. Each of the next $k$ lines holds one meteorite, given by four integers $x$, $y$, $dx$, and $dy$ ($1 \le x \le 10^9$, $\max\{h\} < y \le 10^9$, $-1000 \le dx \le 1000$, $-1000 \le dy \le -1$). Here $(x, y)$ is the current position of the meteorite, $(dx, dy)$ is the slope of the line it falls along, and $\max\{h\}$ is the largest $y$ coordinate among the top sides of the buildings.

Your program writes to standard output. Print exactly one line for each meteorite, in the order given in the input. Each line holds the number of the building that the meteorite collides with. If no building is damaged, print 0.