Rotating Line

There are n points and one line in the 2D plane. Three points can be collinear.
You can rotate the line anti-clockwise, but the rotation centre can be changed every time. The centre must be one of the n points.
Initially the centre is (0, 0) (of course, (0, 0) must be one of the n points), and the line coincides with y axis.
If there is only one point in the line, the line’s rotation centre must be this point.
If the line meets another points, the centre may change to the other point.
If there are k points in this line and the current rotation centre is the p-th point of them (of course, we assume that the k points have already sorted), the next rotation centre will be the (k-p+1)-th point of them.
If p = k – p + 1, we consider that the rotation centre is not changed.
In this problem, you must find the q-th rotation centre’s coordinate.
It is guaranteed that the q-th rotation centre always exists.

The first line contains an integer T (≤100), the number of test cases.
The first line of each test case contains an integer n (1 <= n <= 3000, sum of n over all test cases does not exceed 10000) , the number of points.
The i-th line of the following n lines contains two integers x, y (-100 <= x, y <= 100), the coordinate of the i-th point. One of these n points is (0, 0).
Every two points are different and three points can be collinear.
And the next line contains an integer Q, the number of queries (sum of Q over all test cases does not exceed 10000).
Then Q integers ($q_i$) follow, described above (0 < $q_i $<= 1e9).

Each test case, you must output Q lines and each line contains a pair of integer, the coordinate of qi-th rotation centre.

1
8
0 0
-1 0
-1 2
0 -1
0 1
0 2
1 0
2 0
7
1 2 3 4 5 6 7

-1 2
1 0
0 0
0 1
2 0
-1 0
0 1

Initial rotation centre is (0, 0), and the first rotation centre is (-1, 2), because this line meets (-1, 2) at first.

Then the line meets 2 points (0, 1) and (1, 0), so that there are three points on the line. (-1, 2) is the 1st point of them, so the centre has to change to 3rd point (1, 0),
this is the second rotation centre.

Then the line meets 3 points (-1, 0), (0, 0), (2, 0), so that there are four points on the line. The centre is 3rd point of them, so the next centre will be 2nd point (0, 0),
this is the third rotation centre.

The fourth rotation centre is (0, 1) and the line meets 2 points (-1, 2) and (1, 0).

The centre is 2nd point of 3 points, so the centre was not changed. Then the line meets (2, 0), so the fifth rotation centre is (2, 0).

2017 Multi-University Training Contest - Team 10