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;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
using uint = unsigned;
using ull = unsigned long long;
struct modinfo {
  uint mod, root;
};
template <modinfo const& ref>
struct modular {
  static constexpr uint const& mod = ref.mod;
  static modular root() { return modular(ref.root); }
  uint v;
  modular(ll vv = 0) { s(vv % mod + mod); }
  modular& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  modular operator-() const { return modular() - *this; }
  modular& operator+=(const modular& rhs) { return s(v + rhs.v); }
  modular& operator-=(const modular& rhs) { return s(v + mod - rhs.v); }
  modular& operator*=(const modular& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  modular& operator/=(const modular& rhs) { return *this *= rhs.inv(); }
  modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
  modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
  modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
  modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
  modular pow(ll n) const {
    modular res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  modular inv() const { return pow(mod - 2); }
  friend modular operator+(ll x, const modular& y) { return modular(x) + y; }
  friend modular operator-(ll x, const modular& y) { return modular(x) - y; }
  friend modular operator*(ll x, const modular& y) { return modular(x) * y; }
  friend modular operator/(ll x, const modular& y) { return modular(x) / y; }
  friend ostream& operator<<(ostream& os, const modular& m) {
    return os << m.v;
  }
  friend istream& operator>>(istream& is, modular& m) {
    ll x;
    is >> x;
    m = modular(x);
    return is;
  }
  bool operator<(const modular& r) const { return v < r.v; }
  bool operator==(const modular& r) const { return v == r.v; }
  bool operator!=(const modular& r) const { return v != r.v; }
  explicit operator bool() const { return v; }
};
template <class mint>
ll m2l(mint first) {
  return first.v < mint::mod / 2 ? first.v : ll(first.v) - ll(mint::mod);
}
extern constexpr modinfo base{1000000007, 0};
using mint = modular<base>;
const ll vmax = (1 << 21) + 10;
mint fact[vmax], finv[vmax], invs[vmax];
void initfact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  finv[vmax - 1] = fact[vmax - 1].inv();
  for (ll i = vmax - 2; i >= 0; i--) {
    finv[i] = finv[i + 1] * (i + 1);
  }
  for (ll i = vmax - 1; i >= 1; i--) {
    invs[i] = finv[i] * fact[i - 1];
  }
}
mint choose(ll n, ll k) { return fact[n] * finv[n - k] * finv[k]; }
mint binom(ll first, ll second) {
  return fact[first + second] * finv[first] * finv[second];
}
mint catalan(ll n) {
  return binom(n, n) - (n - 1 >= 0 ? binom(n - 1, n + 1) : 0);
}
ll norm_mod(ll first, ll p) {
  first %= p;
  if (first < 0) first += p;
  return first;
}
ll jacobi(ll first, ll p) {
  first = norm_mod(first, p);
  auto neg = [](ll x) { return x % 2 ? -1 : 1; };
  if (first == 0)
    return p == 1;
  else if (first % 2)
    return neg(((p - 1) & (first - 1)) >> 1) * jacobi(p % first, first);
  else
    return neg(((p & 15) * (p & 15) - 1) / 8) * jacobi(first / 2, p);
}
ll sqrt_mod(ll first, ll p) {
  if (p == 2) return first % 2;
  if (first == 0) return 0;
  if (jacobi(first, p) == -1) return -1;
  ll second, c;
  do {
    second = rand_int(0, p - 1);
    c = norm_mod(second * second - first, p);
  } while (jacobi(c, p) != -1);
  auto mul = [&](pair<ll, ll> x, pair<ll, ll> y) {
    return pi(norm_mod(x.first * y.first + x.second * y.second % p * c, p),
              norm_mod(x.first * y.second + x.second * y.first, p));
  };
  pair<ll, ll> x(second, 1), cur(1, 0);
  ll n = (p + 1) / 2;
  while (n) {
    if (n & 1) cur = mul(cur, x);
    x = mul(x, x);
    n >>= 1;
  }
  assert(cur.second == 0);
  return min(cur.first, p - cur.first);
}
template <class mint>
vc<mint> quadratic_equation(mint first, mint second, mint c) {
  mint d = sq(second) - 4 * first * c;
  ll z = sqrt_mod(d.v, mint::mod);
  if (z == -1) return {};
  vc<mint> res;
  for (ll k = ll(0); k < ll(2); k++) {
    res.push_back((-second + z) / (2 * first));
    if (z == 0) break;
    z = mint::mod - z;
  }
  return res;
}
vc<pair<mint, mint>> cross_circle(mint x1, mint y1, mint z1, mint x2, mint y2,
                                  mint z2) {
  mint first = x2 - x1, second = y2 - y1;
  void(0);
  bool rev = false;
  if (first == 0) {
    rev = true;
    swap(first, second);
  }
  if (first == 0) {
    assert(z1 != z2);
    return {};
  }
  mint w = (z1 + first * first + second * second - z2) / 2;
  auto qs = quadratic_equation(first * first + second * second, -2 * second * w,
                               w * w - first * first * z1);
  vc<pair<mint, mint>> res;
  for (auto q : qs) {
    mint p = (w - second * q) / first;
    if (rev)
      res.emplace_back(q, p);
    else
      res.emplace_back(p, q);
  }
  for (auto& t : res) {
    t.first += x1;
    t.second += y1;
  }
  return res;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  ll n;
  cin >> n;
  vc<pi> xy;
  mint cx, cy, waf;
  for (ll i = ll(0); i < ll(n); i++) {
    ll x, y;
    cin >> x >> y;
    xy.emplace_back(x, y);
    cx += x;
    cy += y;
    waf += x * x + y * y;
  }
  mint in = mint(n).inv();
  cx *= in;
  cy *= in;
  waf *= in;
  ll qs;
  cin >> qs;
  for (ll _ = ll(0); _ < ll(qs); _++) {
    vi ds = readvi(n);
    sort(ds.begin(), ds.end());
    mint cd;
    for (auto v : ds) cd += v;
    cd *= in;
    cd -= waf;
    cd += cx * cx + cy * cy;
    vc<pi> cand;
    for (ll i = ll(0); i < ll(n); i++) {
      auto f = cross_circle(xy[i].first, xy[i].second, ds[0], cx, cy, cd);
      void(0);
      for (auto z : f) {
        ll x = m2l(z.first), y = m2l(z.second);
        if (sq(x - xy[i].first) + sq(y - xy[i].second) == ds[0])
          cand.emplace_back(m2l(z.first), m2l(z.second));
      }
    }
    mkuni(cand);
    vc<pi> tmp;
    for (auto z : cand) {
      vi cur(n);
      for (ll i = ll(0); i < ll(n); i++)
        cur[i] = sq(z.first - xy[i].first) + sq(z.second - xy[i].second);
      sort(cur.begin(), cur.end());
      if (cur == ds) tmp.push_back(z);
    }
    sort(tmp.begin(), tmp.end());
    cout << ll(tmp.size());
    for (auto z : tmp) {
      cout << " " << z.first << " " << z.second;
    }
    cout << "\n";
  }
}