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:
n = input()
x0,y0,sx,sy,s2 = 0,0,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 range(n):
    if (n * qx[i],n * qy[i]) != (sx,sy):
        p,q = qx[i],qy[i]
        break
m = int(input())
a = n * p * 2 - 2 * sx
b = n * q * 2 - 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):
    n = int(x)
    if not n: return 0
    fa,fb = divmod(n.bit_length(),2)
    x = 2 ** (fa + fb)
    while True:
        y = (x + n / x) / 2
        if y >= x:
            return x
        x = y
ans = []
def ghash(x):
    return x * 13331 + 23333
for i in xrange(m):
    d = map(int,raw_input().split())
    sumd = sum(d)
    hd = 0
    for j in d: hd ^= ghash(j)
    ret = []
    for j in xrange(n):
        if j > 0 and d[j] == d[j - 1]: continue
        c = pc + sumd - 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: return
            x,y = x / sr,y / sr
            z = 0
            for k in xrange(n):
                z ^= ghash((x - qx[k]) ** 2 + (y - qy[k]) ** 2)
            if z == hd: ret.append((x,y))
        check(idt)
        if idt: check(-idt)
    ret.sort()
    buf = []
    buf.append(len(ret))
    for x in ret:
        buf.append(x[0])
        buf.append(x[1])
    ans.append(' '.join(map(str,buf)))
print('\n'.join(ans))