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;
int n, m, x[100001], y[100001];
long long d[100001], tem[100001];
std::set<std::pair<long long, long long> > Set;
long double sq(long double x) { return x * x; }
void get(long long x, long long y, long long now) {
  if (1ll * (x - ::x[1]) * (x - ::x[1]) + 1ll * (y - ::y[1]) * (y - ::y[1]) !=
      now)
    return;
  for (int i = 1; i <= n; i++) {
    tem[i] =
        1ll * (x - ::x[i]) * (x - ::x[i]) + 1ll * (y - ::y[i]) * (y - ::y[i]);
  }
  std::sort(tem + 1, tem + n + 1);
  for (int i = 1; i <= n; i++)
    if (tem[i] != d[i]) return;
  Set.insert(std::make_pair(x, y));
}
void calc(long long x, long long y, long long now) {
  for (int i = x - 20; i <= x + 20; i++)
    for (int j = y - 20; j <= y + 20; j++) get(i, j, now);
}
void check(long long x1, long long y1, long double r1, long long x2,
           long long y2, long long r2) {
  long double dis = sq((long double)x2 - ((long double)x1 / (long double)n)) +
                    sq((long double)y2 - ((long double)y1 / (long double)n));
  if (dis > sq(sqrt(r1) + sqrt((long double)r2)) + 1e-6) return;
  long double k =
      std::atan2(((long double)y1 / (long double)n - (long double)y2),
                 ((long double)x1 / (long double)n) - (long double)x2);
  long double p = ((long double)((long double)r2 + dis - r1)) / 2. / sqrt(dis) /
                  sqrt((long double)r2);
  if (p < -1.) p = -1.;
  if (p > 1.) p = 1.;
  p = acos(p);
  long double X, Y;
  X = sqrt((long double)r2) * cos(k + p);
  Y = sqrt((long double)r2) * sin(k + p);
  calc(x2 + (long long)X, y2 + (long long)Y, r2);
  X = sqrt((long double)r2) * cos(k - p);
  Y = sqrt((long double)r2) * sin(k - p);
  calc(x2 + (long long)X, y2 + (long long)Y, r2);
}
int main() {
  scanf("%d", &n);
  long long sx = 0, sy = 0;
  for (int i = 1; i <= n; i++)
    scanf("%d%d", x + i, y + i), sx += x[i], sy += y[i];
  for (int i = 1; i <= n; i++)
    if (1ll * x[i] * n != sx || 1ll * y[i] * n != sy) {
      std::swap(x[1], x[i]);
      std::swap(y[1], y[i]);
      break;
    }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    for (int i = 1; i <= n; i++) scanf("%lld", d + i);
    std::sort(d + 1, d + n + 1);
    long double r = 0.;
    for (int i = 1; i <= n; i++)
      r += (long double)d[i] -
           (sq((long double)x[i] - (long double)sx / (long double)n) +
            sq((long double)y[i] - (long double)sy / (long double)n));
    r /= n;
    Set.clear();
    for (int i = 1; i <= n; i++) {
      if (!d[i])
        calc(x[1], y[1], 0);
      else
        check(sx, sy, r, x[1], y[1], d[i]);
    }
    printf("%d ", Set.size());
    for (auto it = Set.begin(); it != Set.end(); ++it)
      printf("%lld %lld ", it->first, it->second);
    putchar('\n');
  }
}