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 ll = long long;
const int N = 100010;
const long double eps = 1e-9;
int sig(long double p) { return (p > eps) - (p < -eps); }
long double sqr(long double p) { return p * p; }
ll sqr(int p) { return 1ll * p * p; }
struct P {
  long double x, y;
  explicit P(long double x = 0, long double y = 0) : x(x), y(y) {}
  P operator+(const P &p) const { return P(x + p.x, y + p.y); }
  P operator-(const P &p) const { return P(x - p.x, y - p.y); }
  P operator*(const long double &p) const { return P(x * p, y * p); }
  long double operator%(const P &p) const { return x * p.x + y * p.y; }
  long double abs2() const { return *this % *this; }
  P rot90() const { return P(-y, x); }
};
int n;
int x[N], y[N];
struct C {
  P o;
  long double r;
  C(P o, long double r) : o(o), r(r) {}
};
std::vector<P> isCC(C c1, C c2) {
  if (!sig(c1.o.x - c2.o.x) && !sig(c1.o.y - c2.o.y)) {
    return {};
  }
  long double d = (c1.o - c2.o).abs2();
  long double x = ((c1.r - c2.r) / d + 1) / 2;
  long double y = std::max(c1.r / d - sqr(x), 0.0L);
  P q1 = c1.o + (c2.o - c1.o) * x;
  P q2 = ((c2.o - c1.o) * std::sqrt(y)).rot90();
  return {q1 - q2, q1 + q2};
}
void solve() {
  std::vector<ll> dis(n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", &dis[i]);
  }
  std::sort(dis.begin(), dis.end());
  long double avgx = 0, avgy = 0, avgx2 = 0, avgy2 = 0, avgdis = 0;
  for (int i = 0; i < n; ++i) {
    avgx += x[i];
    avgy += y[i];
    avgx2 += sqr(x[i]);
    avgy2 += sqr(y[i]);
    avgdis += dis[i];
  }
  long double r =
      avgdis / n + sqr(avgx / n) + sqr(avgy / n) - avgx2 / n - avgy2 / n;
  C basic(P(avgx / n, avgy / n), r);
  std::vector<P> points;
  using pii = std::pair<int, int>;
  std::vector<pii> ans;
  for (int i = 0; i < n; ++i) {
    C circle(P(x[0], y[0]), dis[i]);
    auto ps = isCC(circle, basic);
    for (auto p : ps) {
      int xx = std::round(p.x), yy = std::round(p.y);
      const int S = 20;
      for (int u = xx - S; u <= xx + S; ++u) {
        for (int v = yy - S; v <= yy + S; ++v) {
          if (sqr(u - x[0]) + sqr(v - y[0]) == dis[i]) {
            ans.emplace_back(u, v);
          }
        }
      }
    }
  }
  std::sort(ans.begin(), ans.end());
  ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
  std::vector<pii> ret;
  for (auto p : ans) {
    std::vector<ll> real_dis(n);
    for (int i = 0; i < n; ++i) {
      real_dis[i] = sqr(p.first - x[i]) + sqr(p.second - y[i]);
    }
    std::sort(real_dis.begin(), real_dis.end());
    if (dis == real_dis) {
      ret.push_back(p);
    }
  }
  printf("%d", (int)ret.size());
  for (auto p : ret) {
    printf(" %d %d", p.first, p.second);
  }
  puts("");
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &x[i], &y[i]);
  }
  int test;
  scanf("%d", &test);
  while (test--) {
    solve();
  }
  return 0;
}