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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 1600002;
const long double eps = 1000, Eps = 1e-8;
struct Uzi {
  int x, y;
  bool operator<(const Uzi &k) const {
    if (k.x != x) return k.x > x;
    return k.y > y;
  }
} p[N];
int n, m, x[N], y[N], i, cnt, ans;
long long d[N], D[N], s8, s9;
long double Cx, Cy, Sxy, Sd, R;
void init() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d%d", x + i, y + i), Cx += x[i], Cy += y[i];
  Cx /= n;
  Cy /= n;
  for (i = 1; i <= n; i++)
    Sxy += (Cx - x[i]) * (Cx - x[i]) + (Cy - y[i]) * (Cy - y[i]);
}
void Check(long long X, long long Y) {
  int i;
  if (fabs((X - Cx) * (X - Cx) + (Y - Cy) * (Y - Cy) - R) > eps) return;
  for (i = 1; i <= n; i++)
    D[i] = 1ll * (X - x[i]) * (X - x[i]) + 1ll * (Y - y[i]) * (Y - y[i]);
  sort(D + 1, D + n + 1);
  for (i = 1; i <= n; i++)
    if (D[i] != d[i]) return;
  cnt++;
  p[cnt] = (Uzi){(int)X, (int)Y};
}
void GetNode(long double X1, long double Y1, long double R1, long double X2,
             long double Y2, long double R2, long double R12, long double R22) {
  long double dis = sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2));
  long double dis2 = (X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2);
  if (dis > R1 + R2 + Eps) return;
  long double t = atan2(Y2 - Y1, X2 - X1);
  long double p = (R12 + dis2 - R22) / 2 / R1 / dis;
  if (p > 1) p = 1;
  if (p < -1) p = -1;
  long double k = acos(p);
  long double X3 = X1 + R1 * cos(t + k);
  long double Y3 = Y1 + R1 * sin(t + k);
  int u, v;
  if (fabs(X3) < (1e10) && fabs(Y3) < (1e10)) {
    for (u = -5; u <= 5; u++)
      for (v = -5; v <= 5; v++) {
        Check((long long)(X3 + u), (long long)(Y3 + v));
      }
  }
  long double X4 = X1 + R1 * cos(t - k);
  long double Y4 = Y1 + R1 * sin(t - k);
  if (fabs(X4) < (1e10) && fabs(Y4) < (1e10)) {
    for (u = -5; u <= 5; u++)
      for (v = -5; v <= 5; v++) {
        Check((long long)(X4 + u), (long long)(Y4 + v));
      }
  }
}
void work() {
  cnt = 0;
  Sd = 0;
  ans = 0;
  s8 = s9 = 0;
  for (i = 1; i <= n; i++) {
    scanf("%lld", d + i);
    s8 += d[i] / 1000000000;
    s9 += d[i] % 1000000000;
  }
  sort(d + 1, d + n + 1);
  d[0] = 233333333;
  R = (((long double)s8) * ((long double)1000000000) + ((long double)s9) -
       Sxy) /
      n;
  for (i = 1; i <= n; i++)
    if (d[i] != d[i - 1])
      GetNode(Cx, Cy, sqrt(R), x[1], y[1], sqrt(d[i]), R, d[i]);
  p[0].x = p[0].y = 192608170;
  sort(p + 1, p + cnt + 1);
  for (i = 1; i <= cnt; i++)
    if (p[i].x != p[i - 1].x || p[i].y != p[i - 1].y) ans++;
  printf("%d ", ans);
  for (i = 1; i <= cnt; i++)
    if (p[i].x != p[i - 1].x || p[i].y != p[i - 1].y)
      printf("%d %d ", p[i].x, p[i].y);
  printf("\n");
}
int main() {
  init();
  scanf("%d", &m);
  while (m--) work();
  return 0;
}