Rotating Line

Consider an infinite two-dimensional plane. There are $n$ fixed points and one rotating line on the plane. One of the points is $(0, 0)$, the origin, and the line initially coincides with the $y$ axis. The points are distinct, but it is not guaranteed that no three points lie on the same line.

The line rotates counter-clockwise. The centre of rotation is always one of the $n$ given points, and it is initially the origin. It may change. While the line contains only one point, the rotation centre is that point. As soon as the line meets another point, consider all given points currently on the line, sorted by their coordinates $(x, y)$. If there are $k$ points on the line and the current rotation centre is the $p$-th of them (counting from 1), the next rotation centre is the $(k - p + 1)$-th of these points. If $p = k - p + 1$, the rotation centre does not change. The line starts rotating even if several given points already lie on it at the start.

Your task is to find the $q$-th rotation centre. The initial centre is numbered 0. As long as the centre does not change, the counter does not increase. It is guaranteed that the $q$-th rotation centre exists for the given set of points.

The first line contains an integer $n$, the number of points ($2 \le n \le 3000$).

Each of the following $n$ lines contains two integers $x$ and $y$, the coordinates of a point ($-100 \le x, y \le 100$). One of these points is $(0, 0)$. The points are distinct, but it is not guaranteed that no three points lie on the same line.

The next line contains an integer $Q$, the number of queries ($1 \le Q \le 2700$). Each of the following $Q$ lines contains a single integer $q_i$ ($0 < q_i \le 10^9$). The queries are given in strictly ascending order.

Print $Q$ lines, one for each query. Each line contains a pair of integers: the coordinates of the $q_i$-th rotation centre.

The initial rotation centre (numbered 0) is $(0, 0)$. The rotation centre number 1 is $(-1, 2)$, because it is the first point the line meets.

Then the line meets two points $(0, 1)$ and $(1, 0)$ at the same time, so there are three points on the line. $(-1, 2)$ is the first of them in sorted order, so the centre changes to the third point, $(1, 0)$. Thus, $(1, 0)$ is the rotation centre number 2.

Then the line meets three points $(-1, 0)$, $(0, 0)$, and $(2, 0)$, so there are four points on the line. The centre is the third of them in sorted order, so the centre number 3 is the second of the four points, $(0, 0)$.

Similarly, the 4th rotation centre is $(0, 1)$.

After that, the line meets two points $(-1, 2)$ and $(1, 0)$. The centre is the second of three points in sorted order, so it does not change.

After that, the line meets $(2, 0)$, so the 5th rotation centre is $(2, 0)$.