Problem: 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

The first line of input contains a single integer n (2 ≤ n ≤ 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 ≤ x_i,y_i ≤ 10^8). It is guaranteed that no two antennas coincide.

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

Following m lines contain n integers 0 ≤ d_1 ≤ d_2 ≤ ... ≤ d_n ≤ 2 ⋅ 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 ≤ x, y ≤ 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.

Examples

Input


3
0 0
0 1
1 0
1
1 1 2


Output


1 1 1 


Input


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


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.

Solution (in PYTHON):

Solution:
from sys import stdin, stdout  
 
n=input()
 
x0,y0=0,0
sx,sy,s2=0,0,0
 
qx=[0]*n
qy=[0]*n
 
for i in xrange(n):
	px,py=map(int,raw_input().split())
	qx[i],qy[i]=px,py
	sx+=px
	sy+=py
	s2+=qx[i]*qx[i]+qy[i]*qy[i]
 
 
for i in xrange(n):
	if (n*qx[i],n*qy[i])!=(sx,sy):
		p,q=qx[i],qy[i]
		break
 
m=input()
a=2*p*n-2*sx
b=2*q*n-2*sy
pc=n*(p*p+q*q)-s2
pdt=-(a*a*p*p+2*a*b*p*q+b*b*q*q)
sr=a*a+b*b
 
def isqrt(x):
    nn = int(x)
    if nn == 0:
        return 0
    fa, fb = divmod(nn.bit_length(), 2)
    x = 2**(fa+fb)
    while True:
        y = (x + nn/x)/2
        if y >= x:
            return x
        x = y
pans=[]
 
def gethash(x):
	return x*13331+23333
 
for i in xrange(m):
	d=map(int,raw_input().split())
	sd=sum(d)
	hd=0
	for j in xrange(n):
		hd^=gethash(d[j])
	ans=[]
	for j in xrange(n):
		if j>=1 and d[j]==d[j-1]: continue
		c=pc+sd-n*d[j]
		dt=pdt+a*a*d[j]+2*a*c*p+b*b*d[j]+2*b*c*q-c*c
		if dt<0: continue
		idt=isqrt(dt)
		if idt*idt!=dt:
			continue
		def check(idt):
			x=(b*idt-a*b*q+a*c+b*b*p)
			y=(-a*idt+a*a*q+b*c-a*b*p)
			if x%sr!=0:
				return
			x,y=x/sr,y/sr
			z=0
			for k in xrange(n):
				z^=gethash((x-qx[k])**2+(y-qy[k])**2)
			if z==hd:
				ans.append([x,y])
		check(idt)
		if idt!=0: check(-idt)
	ans.sort()
	buf=[]
	buf.append(len(ans))
	for x in ans:
		buf.append(x[0])
		buf.append(x[1])
	pans.append(" ".join(map(str,buf)))
stdout.write("\n".join(pans))