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 mn = 1e5 + 10;
long long x[mn], y[mn], d[mn];
inline long double sq(long double x) { return x * x; }
inline long long sq(long long x) { return x * x; }
long double eps = 1e-8;
long double i1x, i1y, i2x, i2y;
vector<pair<long long, long long> > ans;
void idk(long long xx, long long yy, int i, int n) {
  if (sq(xx - x[0]) + sq(yy - y[0]) != d[i]) return;
  vector<long long> v;
  for (int j = 0; j < n; j++) v.push_back(sq(xx - x[j]) + sq(yy - y[j]));
  sort(v.begin(), v.end());
  for (int j = 0; j < n; j++)
    if (d[j] != v[j]) return;
  ans.push_back({xx, yy});
}
void intersect(long double x1, long double y1, long double r1, long double x2,
               long double y2, long double r2, long double r12, long double r22,
               int i, int n) {
  long double dis = sqrt(sq(x1 - x2) + sq(y1 - y2));
  long double dis2 = sq(x1 - x2) + sq(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);
  i1x = x1 + r1 * cos(t + k);
  i1y = y1 + r1 * sin(t + k);
  i2x = x1 + r1 * cos(t - k);
  i2y = y1 + r1 * sin(t - k);
  if (fabs(i1x) + fabs(i1y) < 1e9)
    for (int j = -6; j <= 6; j++) {
      for (int k = -6; k <= 6; k++) {
        idk((long long)i1x + j, (long long)i1y + k, i, n);
      }
    }
  if (fabs(i2x) + fabs(i2y) < 1e9)
    for (int j = -6; j <= 6; j++) {
      for (int k = -6; k <= 6; k++) {
        idk((long long)i2x + j, (long long)i2y + k, i, n);
      }
    }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lld%lld", x + i, y + i);
  long double sx = 0, sy = 0, sxy = 0;
  for (int i = 0; i < n; i++) sx += x[i], sy += y[i];
  long double cx = sx / n, cy = sy / n;
  for (int i = 0; i < n; i++) sxy += sq(cx - x[i]) + sq(cy - y[i]);
  int m;
  scanf("%d", &m);
  while (m--) {
    ans.clear();
    for (int i = 0; i < n; i++) scanf("%lld", d + i);
    long long h1 = 0, h2 = 0;
    for (int i = 0; i < n; i++)
      h1 += d[i] / 1000000000, h2 += d[i] % 1000000000;
    long double r2 = (((long double)h1) * 1e9 + ((long double)(h2)-sxy)) / n;
    for (int i = 0; i < n; i++) {
      if (i && d[i] == d[i - 1]) continue;
      intersect(cx, cy, sqrt(r2), x[0], y[0], sqrt(d[i]), r2, d[i], i, n);
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    printf("%d", ans.size());
    for (auto hail : ans) printf(" %lld %lld", hail.first, hail.second);
    printf("\n");
  }
}