Geolocation
Contest: Codeforces Round 586 (Div. 1 + Div. 2)
Difficulty rating: 3400
Tags: geometry

You are working for the Gryzzl company, headquartered in Pawnee, Indiana.

The new national park has been opened near Pawnee recently and you are to implement a geolocation system, so people won't get lost. The concept you developed is innovative and minimalistic. There will be $$$n$$$ antennas located somewhere in the park. When someone would like to know their current location, their Gryzzl hologram phone will communicate with antennas and obtain distances from a user's current location to all antennas.

Knowing those distances and antennas locations it should be easy to recover a user's location... Right? Well, almost. The only issue is that there is no way to distinguish antennas, so you don't know, which distance corresponds to each antenna. Your task is to find a user's location given as little as all antennas location and an unordered multiset of distances.

Input format:
The first line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) which is the number of antennas.

The following $$$n$$$ lines contain coordinates of antennas, $$$i$$$-th line contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq x_i,y_i \leq 10^8$$$). It is guaranteed that no two antennas coincide.

The next line of input contains integer $$$m$$$ ($$$1 \leq n \cdot m \leq 10^5$$$), which is the number of queries to determine the location of the user.

Following $$$m$$$ lines contain $$$n$$$ integers $$$0 \leq d_1 \leq d_2 \leq \dots \leq d_n \leq 2 \cdot 10^{16}$$$ each. These integers form a multiset of squared distances from unknown user's location $$$(x;y)$$$ to antennas.

For all test cases except the examples it is guaranteed that all user's locations $$$(x;y)$$$ were chosen uniformly at random, independently from each other among all possible integer locations having $$$0 \leq x, y \leq 10^8$$$.

Output format:
For each query output $$$k$$$, the number of possible a user's locations matching the given input and then output the list of these locations in lexicographic order.

It is guaranteed that the sum of all $$$k$$$ over all points does not exceed $$$10^6$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
As you see in the second example, although initially a user's location is picked to have non-negative coordinates, you have to output all possible integer locations.

Example input:
3
0 0
0 1
1 0
1
1 1 2

Example output:
1 1 1

Example input:
4
0 0
0 1
1 0
1 1
2
0 1 1 2
2 5 5 8

Example output:
4 0 0 0 1 1 0 1 1 
4 -1 -1 -1 2 2 -1 2 2

Editorial:
Let's look on the sum of squared distances from unknown point $$$(x;y)$$$ to all known points $$$(x_i;y_i)$$$:
$$$$$$\sum\limits_{i=1}^n d_i^2 = \sum\limits_{i=1}^n\left((x-x_i)^2+(y-y_i)^2\right)= n(x^2+y^2)-2x\sum\limits_{i=1}^n x_i - 2y\sum\limits_{i=1}^n y_i + \sum\limits_{i=1}^n (x_i^2+y_i^2)$$$$$$
If we switch to new coordinates with the origin in the center of mass of all points, terms $$$\sum\limits_{i=1}^n x_i$$$ and $$$\sum\limits_{i=1}^n y_i$$$ will be equal to zero, thus the whole sum will be equal to: $$$$$$\sum\limits_{i=1}^n d_i^2 = n(x^2+y^2)+\sum\limits_{i=1}^n(x_i^2+y_i^2)$$$$$$
From this we obtain that all possible points $$$(x;y)$$$ lie on the circumference with the center in the center of mass of all points with the squared radius equal to $$$\frac{1}{n}\sum\limits_{i=1}^n (d_i^2-x_i^2-y_i^2)$$$. Due to the randomness of unknown point we may assume that there is only as much as $$$\log n$$$ integer points on this circumference. If we try all possible distances from first point, we may reduce possible points to only those found on the intersection of two circumferences.