#include <bits/stdc++.h>

using namespace std;

const int S = 200;

class point {
 public:
  int x, y;

  point(int x = 0, int y = 0): x(x), y(y) {
  }

  point operator - (const point &b) const {
    return point(x - b.x, y - b.y);
  }

  long long operator * (const point &b) const {
    return (long long) x * b.y - (long long) y * b.x;
  }

  bool operator < (const point &b) const {
    return x < b.x || (x == b.x && y < b.y);
  }
};

long long dist(point u, point v) {
  return (long long) (u.x - v.x) * (u.x - v.x) + (long long) (u.y - v.y) * (u.y - v.y);
}

long long cross(point u, point v, point o) {
  return (u - o) * (v - o);
}

class convex_hull {
 public:
  vector<point> up;
  vector<point> down;

  convex_hull() {
  }

  convex_hull(vector<point> all) {
    up = all;
    down = all;
    build();
  }

  convex_hull operator + (const convex_hull &b) const {
    convex_hull c;
    c.up.resize(up.size() + b.up.size());
    merge(up.begin(), up.end(), b.up.begin(), b.up.end(), c.up.begin());
    c.down.resize(down.size() + b.down.size());
    merge(down.begin(), down.end(), b.down.begin(), b.down.end(), c.down.begin());
    c.build();
    return c;
  }

  void build() {
    {
      int n = up.size();
      int m = 0;
      for (int i = 0; i < n; ++i) {
        while (m > 1 && cross(up[i], up[m - 1], up[m - 2]) <= 0) {
          --m;
        }
        up[m++] = up[i];
      }
      up.resize(m);
    }
    {
      int n = down.size();
      int m = 0;
      for (int i = 0; i < n; ++i) {
        while (m > 1 && cross(down[i], down[m - 1], down[m - 2]) >= 0) {
          --m;
        }
        down[m++] = down[i];
      }
      down.resize(m);
    }
  }

  long long solve() {
    vector<point> hull = up;
    for (int i = down.size() - 2; ~i; --i) {
      hull.push_back(down[i]);
    }
    reverse(hull.begin(), hull.end());
    int n = hull.size() - 1;
    long long ans = 0;
    for (int i = 0, j = 1; i < n; ++i) {
      while (dist(hull[i], hull[j + 1]) > dist(hull[i], hull[j])) {
      	j = (j + 1) % n;
      }
      ans = max(ans, dist(hull[i], hull[j]));
      ans = max(ans, dist(hull[i + 1], hull[j + 1]));
    }
    return ans;
  }
};

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  scanf("%d", &n);
  vector<point> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", &a[i].x, &a[i].y);
  }
  int m = (n - 1) / S + 1;
  vector<vector<pair<point, int>>> sorted(m);
  for (int i = 0; i < m; ++i) {
    int l = i * S, r = min((i + 1) * S, n);
    for (int j = l; j < r; ++j) {
      sorted[i].emplace_back(a[j], j);
    }
    sort(sorted[i].begin(), sorted[i].end());
  }
  vector<int> len(m + 1);
  for (int i = 2; i <= m; ++i) {
    len[i] = len[i >> 1] + 1;
  }
  vector<vector<convex_hull>> rmq(len[m] + 1, vector<convex_hull>(m));
  for (int i = 0; i < m; ++i) {
    vector<point> points;
    for (auto p : sorted[i]) {
      points.push_back(p.first);
    }
    rmq[0][i] = convex_hull(points);
  }
  for (int i = 1; i <= len[m]; ++i) {
    for (int j = 0; j + (1 << i) <= m; ++j) {
      rmq[i][j] = rmq[i - 1][j] + rmq[i - 1][j + (1 << i - 1)];
    }
  }
  auto get_rmq = [&](int l, int r) {
    if (l > r) {
      return convex_hull();
    }
    int k = len[r - l + 1];
    return rmq[k][l] + rmq[k][r - (1 << k) + 1];
  };
  int q;
  scanf("%d", &q);
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    --l;
    --r;
    if (l / S == r / S) {
      vector<point> points;
      for (auto p : sorted[l / S]) {
        if (p.second >= l && p.second <= r) {
          points.push_back(p.first);
        }
      }
      convex_hull res(points);
      printf("%lld\n", res.solve());
    } else {
      vector<point> points_l;
      for (auto p : sorted[l / S]) {
        if (p.second >= l) {
          points_l.push_back(p.first);
        }
      }
      vector<point> points_r;
      for (auto p : sorted[r / S]) {
        if (p.second <= r) {
          points_r.push_back(p.first);
        }
      }
      convex_hull res = get_rmq(l / S + 1, r / S - 1) + convex_hull(points_l) + convex_hull(points_r);
      printf("%lld\n", res.solve());
    }
  }
  return 0;
}