Geolocation

Description:

Input:

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:

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$$$.

Sample Input:

3
0 0
0 1
1 0
1
1 1 2

Sample Output:

1 1 1 

Sample Input:

4
0 0
0 1
1 0
1 1
2
0 1 1 2
2 5 5 8

Sample Output:

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

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.