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 inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
void precalc() {}
struct point {
  long long x, y;
  point() : x(0), y(0) {}
  point(long long xx, long long yy) : x(xx), y(yy) {}
  bool read() { return scanf("%lld%lld", &x, &y) == 2; }
  point operator+(const point &p) const { return point(x + p.x, y + p.y); }
  point operator-(const point &p) const { return point(x - p.x, y - p.y); }
  point operator*(long long k) const { return point(x * k, y * k); }
  point operator/(long long k) const { return point(x / k, y / k); }
  __int128 operator^(const point &p) const {
    return (__int128)x * p.y - (__int128)y * p.x;
  }
  __int128 operator*(const point &p) const {
    return (__int128)x * p.x + (__int128)y * p.y;
  }
  __int128 slen() const { return *this * *this; }
  bool operator==(const point &p) const { return x == p.x && y == p.y; }
  bool operator<(const point &p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
};
void intersect(point p0, __int128 rr0, point p1, __int128 rr1,
               vector<point> &ans) {
  if (rr0 < rr1) {
    swap(p0, p1);
    swap(rr0, rr1);
  }
  __int128 dd = (p1 - p0).slen();
  long double r0 = sqrt((long double)rr0), r1 = sqrt((long double)rr1);
  long double d = sqrt((long double)dd);
  if (r0 + r1 < d - eps) {
    return;
  }
  if (r1 + d < r0 - eps) {
    return;
  }
  long double cosa = (rr0 + dd - rr1) / (2 * r0 * d);
  long double sina = sqrt(max((long double)0, 1 - cosa * cosa));
  long double vx = (p1 - p0).x / d * r0;
  long double vy = (p1 - p0).y / d * r0;
  long double ux = -vy, uy = vx;
  vx *= cosa;
  vy *= cosa;
  ux *= sina;
  uy *= sina;
  for (int dir = -1; dir <= 1; dir += 2) {
    long double x = p0.x + vx + dir * ux;
    long double y = p0.y + vy + dir * uy;
    point cur((long long)round(x), (long long)round(y));
    if ((cur - p0).slen() == rr0 && (cur - p1).slen() == rr1) {
      ans.push_back(cur);
    }
  }
}
const int maxn = (int)1e5 + 5;
int n;
point ps[maxn];
bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    ps[i].read();
    ps[i] = ps[i] * n;
  }
  return true;
}
point c;
__int128 s;
__int128 d[maxn];
map<__int128, int> cnt, cnt1;
vector<point> ans;
bool check(const point &p) {
  if (p.x % n || p.y % n) {
    return false;
  }
  cnt1.clear();
  for (int i = 0; i < n; i++) {
    __int128 dd = (ps[i] - p).slen();
    auto &cur = cnt1[dd];
    cur++;
    if (cur > cnt[dd]) {
      return false;
    }
  }
  return true;
}
void solve1() {
  __int128 dc = 0;
  cnt.clear();
  for (int i = 0; i < n; i++) {
    long long dd;
    scanf("%lld", &dd);
    d[i] = dd;
    d[i] *= (__int128)n * n;
    dc += d[i];
    cnt[d[i]]++;
  }
  dc /= n;
  dc -= s;
  dc += c.slen();
  ans.clear();
  for (auto it = cnt.begin(); it != cnt.end(); it++) {
    intersect(ps[0], it->first, c, dc, ans);
  }
  sort(ans.begin(), ans.end());
  ans.erase(unique(ans.begin(), ans.end()), ans.end());
  int k = 0;
  for (int i = 0; i < ((int)(ans).size()); i++) {
    if (check(ans[i])) {
      ans[k++] = ans[i] / n;
    }
  }
  ans.resize(k);
  printf("%d ", k);
  for (int i = 0; i < k; i++) {
    printf("%lld %lld ", ans[i].x, ans[i].y);
  }
  printf("\n");
}
void solve() {
  shuffle(ps, ps + n, mrand);
  c = point();
  s = 0;
  for (int i = 0; i < n; i++) {
    c = c + ps[i];
    s += ps[i].slen();
  }
  c = c / n;
  s /= n;
  if (ps[0] == c) {
    swap(ps[0], ps[1]);
  }
  assert(!(ps[0] == c));
  int q;
  scanf("%d", &q);
  for (int qq = 0; qq < q; qq++) {
    solve1();
  }
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}