#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
struct segt_max {
  int tl;
  vector<long long> t;
  long long task(long long child1, long long child2) {
    return max(child1, child2);
  }
  void update(int node, int l, int r, int pos, long long val) {
    if (l == r) {
      t[node] = max(t[node], val);
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        update(node << 1, l, mid, pos, val);
      } else {
        update((node << 1) + 1, mid + 1, r, pos, val);
      }
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void update(int pos, long long val) { update(1, 0, tl - 1, pos, val); }
  long long query(int node, int l, int r, int lq, int rq) {
    if (lq > rq) {
      return -infinity;
    } else if (lq <= l && rq >= r) {
      return t[node];
    } else {
      int mid = (l + r) >> 1;
      return task(query(node << 1, l, mid, lq, min(rq, mid)),
                  query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
    }
  }
  long long query(int lq, int rq) { return query(1, 0, tl - 1, lq, rq); }
  void build(vector<long long>& v, int node, int l, int r) {
    if (l == r) {
      t[node] = v[l];
    } else {
      int mid = (l + r) >> 1;
      build(v, node << 1, l, mid);
      build(v, (node << 1) + 1, mid + 1, r);
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void build(vector<long long>& v) { build(v, 1, 0, tl - 1); }
};
struct segt_min {
  int tl;
  vector<long long> t;
  long long task(long long child1, long long child2) {
    return min(child1, child2);
  }
  void update(int node, int l, int r, int pos, long long val) {
    if (l == r) {
      t[node] = min(t[node], val);
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        update(node << 1, l, mid, pos, val);
      } else {
        update((node << 1) + 1, mid + 1, r, pos, val);
      }
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void update(int pos, long long val) { update(1, 0, tl - 1, pos, val); }
  long long query(int node, int l, int r, int lq, int rq) {
    if (lq > rq) {
      return infinity;
    } else if (lq <= l && rq >= r) {
      return t[node];
    } else {
      int mid = (l + r) >> 1;
      return task(query(node << 1, l, mid, lq, min(rq, mid)),
                  query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
    }
  }
  long long query(int lq, int rq) { return query(1, 0, tl - 1, lq, rq); }
  void build(vector<long long>& v, int node, int l, int r) {
    if (l == r) {
      t[node] = v[l];
    } else {
      int mid = (l + r) >> 1;
      build(v, node << 1, l, mid);
      build(v, (node << 1) + 1, mid + 1, r);
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void build(vector<long long>& v) { build(v, 1, 0, tl - 1); }
};
vector<int> temp_mapper, mapper;
int get_index(int value) {
  return lower_bound(mapper.begin(), mapper.end(), value) - mapper.begin();
}
int coordinate_compression(vector<long long>& v, int len) {
  temp_mapper.reserve(len);
  mapper.reserve(len);
  for (int i = 0; i < len; i++) {
    temp_mapper.push_back(v[i]);
  }
  sort(temp_mapper.begin(), temp_mapper.end());
  mapper.push_back(temp_mapper[0]);
  for (int i = 1; i < len; i++) {
    if (temp_mapper[i] != temp_mapper[i - 1]) mapper.push_back(temp_mapper[i]);
  }
  return mapper.size();
}
bool homelander_sort_1(array<long long, 4> a, array<long long, 4> b) {
  if (a[0] == b[0]) {
    if (a[2] < b[2])
      return true;
    else
      return false;
  } else {
    if (a[0] < b[0])
      return true;
    else
      return false;
  }
}
bool homelander_sort_2(array<long long, 4> a, array<long long, 4> b) {
  if (a[0] == b[0]) {
    if (a[2] < b[2])
      return true;
    else
      return false;
  } else {
    if (a[0] > b[0])
      return true;
    else
      return false;
  }
}
const int maxn = 1e5 + 5;
long long dist[maxn] = {0};
void solve() {
  long long n, m;
  long long nh, nr;
  cin >> n >> m;
  cin >> nh;
  vector<pair<long long, long long>> hotels(nh);
  vector<long long> tot;
  for (int i = 0; i < nh; i++) {
    cin >> hotels[i].first >> hotels[i].second;
    tot.push_back(hotels[i].first);
    tot.push_back(hotels[i].second);
  }
  cin >> nr;
  vector<pair<long long, long long>> restaurants(nr);
  for (int i = 0; i < nr; i++) {
    cin >> restaurants[i].first >> restaurants[i].second;
    tot.push_back(restaurants[i].first);
    tot.push_back(restaurants[i].second);
  }
  int unq = coordinate_compression(tot, tot.size());
  vector<array<long long, 4>> combined;
  combined.reserve(nh + nr);
  for (int i = 0; i < nh; i++) {
    combined.push_back({hotels[i].first, hotels[i].second, 0, i});
  }
  for (int i = 0; i < nr; i++) {
    combined.push_back({restaurants[i].first, restaurants[i].second, 1, i});
  }
  sort(combined.begin(), combined.end(), homelander_sort_1);
  segt_max tq1;
  segt_min tq3;
  tq1.tl = unq;
  tq3.tl = unq;
  tq1.t = vector<long long>(unq << 2, -infinity);
  tq3.t = vector<long long>(unq << 2, infinity);
  for (int i = 0; i < nh + nr; i++) {
    if (combined[i][2]) {
      int index = get_index(combined[i][1]);
      long long d1 =
          tq1.query(index, unq - 1) + (combined[i][0] - combined[i][1]);
      long long d2 = (combined[i][0] + combined[i][1]) - (tq3.query(0, index));
      dist[combined[i][3]] = max(d1, d2);
    } else {
      int index = get_index(combined[i][1]);
      tq1.update(index, combined[i][1] - combined[i][0]);
      tq3.update(index, combined[i][0] + combined[i][1]);
    }
  }
  sort(combined.begin(), combined.end(), homelander_sort_2);
  segt_max tq2, tq4;
  tq2.tl = unq;
  tq4.tl = unq;
  tq2.t = vector<long long>(unq << 2, -infinity);
  tq4.t = vector<long long>(unq << 2, -infinity);
  for (int i = 0; i < nh + nr; i++) {
    if (combined[i][2]) {
      int index = get_index(combined[i][1]);
      long long d1 =
          tq2.query(index, unq - 1) - (combined[i][0] + combined[i][1]);
      long long d2 = (combined[i][1] - combined[i][0]) + (tq4.query(0, index));
      dist[combined[i][3]] = max(dist[combined[i][3]], max(d1, d2));
    } else {
      int index = get_index(combined[i][1]);
      tq2.update(index, combined[i][1] + combined[i][0]);
      tq4.update(index, combined[i][0] - combined[i][1]);
    }
  }
  long long ansi = 0;
  for (int i = 0; i < nr; i++) {
    if (dist[i] < dist[ansi]) {
      ansi = i;
    }
  }
  cout << dist[ansi] << "\n" << ansi + 1 << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q = 1;
  while (q-- > 0) {
    solve();
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

Think of New York as a rectangular grid consisting of N vertical avenues numerated from 1 to N and M horizontal streets numerated 1 to M. C friends are staying at C hotels located at some street-avenue crossings. They are going to celebrate birthday of one of them in the one of H restaurants also located at some street-avenue crossings. They also want that the maximum distance covered by one of them while traveling to the restaurant to be minimum possible. Help friends choose optimal restaurant for a celebration.

Suppose that the distance between neighboring crossings are all the same equal to one kilometer.

Input

The first line contains two integers N и M — size of the city (1 ≤ N, M ≤ 109). In the next line there is a single integer C (1 ≤ C ≤ 105) — the number of hotels friends stayed at. Following C lines contain descriptions of hotels, each consisting of two coordinates x and y (1 ≤ x ≤ N, 1 ≤ y ≤ M). The next line contains an integer H — the number of restaurants (1 ≤ H ≤ 105). Following H lines contain descriptions of restaurants in the same format.

Several restaurants and hotels may be located near the same crossing.

Output

In the first line output the optimal distance. In the next line output index of a restaurant that produces this optimal distance. If there are several possibilities, you are allowed to output any of them.

Examples

Input

10 10
2
1 1
3 3
2
1 10
4 4


Output

6
2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
struct segt_max {
  int tl;
  vector<long long> t;
  long long task(long long child1, long long child2) {
    return max(child1, child2);
  }
  void update(int node, int l, int r, int pos, long long val) {
    if (l == r) {
      t[node] = max(t[node], val);
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        update(node << 1, l, mid, pos, val);
      } else {
        update((node << 1) + 1, mid + 1, r, pos, val);
      }
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void update(int pos, long long val) { update(1, 0, tl - 1, pos, val); }
  long long query(int node, int l, int r, int lq, int rq) {
    if (lq > rq) {
      return -infinity;
    } else if (lq <= l && rq >= r) {
      return t[node];
    } else {
      int mid = (l + r) >> 1;
      return task(query(node << 1, l, mid, lq, min(rq, mid)),
                  query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
    }
  }
  long long query(int lq, int rq) { return query(1, 0, tl - 1, lq, rq); }
  void build(vector<long long>& v, int node, int l, int r) {
    if (l == r) {
      t[node] = v[l];
    } else {
      int mid = (l + r) >> 1;
      build(v, node << 1, l, mid);
      build(v, (node << 1) + 1, mid + 1, r);
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void build(vector<long long>& v) { build(v, 1, 0, tl - 1); }
};
struct segt_min {
  int tl;
  vector<long long> t;
  long long task(long long child1, long long child2) {
    return min(child1, child2);
  }
  void update(int node, int l, int r, int pos, long long val) {
    if (l == r) {
      t[node] = min(t[node], val);
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        update(node << 1, l, mid, pos, val);
      } else {
        update((node << 1) + 1, mid + 1, r, pos, val);
      }
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void update(int pos, long long val) { update(1, 0, tl - 1, pos, val); }
  long long query(int node, int l, int r, int lq, int rq) {
    if (lq > rq) {
      return infinity;
    } else if (lq <= l && rq >= r) {
      return t[node];
    } else {
      int mid = (l + r) >> 1;
      return task(query(node << 1, l, mid, lq, min(rq, mid)),
                  query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
    }
  }
  long long query(int lq, int rq) { return query(1, 0, tl - 1, lq, rq); }
  void build(vector<long long>& v, int node, int l, int r) {
    if (l == r) {
      t[node] = v[l];
    } else {
      int mid = (l + r) >> 1;
      build(v, node << 1, l, mid);
      build(v, (node << 1) + 1, mid + 1, r);
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  void build(vector<long long>& v) { build(v, 1, 0, tl - 1); }
};
vector<int> temp_mapper, mapper;
int get_index(int value) {
  return lower_bound(mapper.begin(), mapper.end(), value) - mapper.begin();
}
int coordinate_compression(vector<long long>& v, int len) {
  temp_mapper.reserve(len);
  mapper.reserve(len);
  for (int i = 0; i < len; i++) {
    temp_mapper.push_back(v[i]);
  }
  sort(temp_mapper.begin(), temp_mapper.end());
  mapper.push_back(temp_mapper[0]);
  for (int i = 1; i < len; i++) {
    if (temp_mapper[i] != temp_mapper[i - 1]) mapper.push_back(temp_mapper[i]);
  }
  return mapper.size();
}
bool homelander_sort_1(array<long long, 4> a, array<long long, 4> b) {
  if (a[0] == b[0]) {
    if (a[2] < b[2])
      return true;
    else
      return false;
  } else {
    if (a[0] < b[0])
      return true;
    else
      return false;
  }
}
bool homelander_sort_2(array<long long, 4> a, array<long long, 4> b) {
  if (a[0] == b[0]) {
    if (a[2] < b[2])
      return true;
    else
      return false;
  } else {
    if (a[0] > b[0])
      return true;
    else
      return false;
  }
}
const int maxn = 1e5 + 5;
long long dist[maxn] = {0};
void solve() {
  long long n, m;
  long long nh, nr;
  cin >> n >> m;
  cin >> nh;
  vector<pair<long long, long long>> hotels(nh);
  vector<long long> tot;
  for (int i = 0; i < nh; i++) {
    cin >> hotels[i].first >> hotels[i].second;
    tot.push_back(hotels[i].first);
    tot.push_back(hotels[i].second);
  }
  cin >> nr;
  vector<pair<long long, long long>> restaurants(nr);
  for (int i = 0; i < nr; i++) {
    cin >> restaurants[i].first >> restaurants[i].second;
    tot.push_back(restaurants[i].first);
    tot.push_back(restaurants[i].second);
  }
  int unq = coordinate_compression(tot, tot.size());
  vector<array<long long, 4>> combined;
  combined.reserve(nh + nr);
  for (int i = 0; i < nh; i++) {
    combined.push_back({hotels[i].first, hotels[i].second, 0, i});
  }
  for (int i = 0; i < nr; i++) {
    combined.push_back({restaurants[i].first, restaurants[i].second, 1, i});
  }
  sort(combined.begin(), combined.end(), homelander_sort_1);
  segt_max tq1;
  segt_min tq3;
  tq1.tl = unq;
  tq3.tl = unq;
  tq1.t = vector<long long>(unq << 2, -infinity);
  tq3.t = vector<long long>(unq << 2, infinity);
  for (int i = 0; i < nh + nr; i++) {
    if (combined[i][2]) {
      int index = get_index(combined[i][1]);
      long long d1 =
          tq1.query(index, unq - 1) + (combined[i][0] - combined[i][1]);
      long long d2 = (combined[i][0] + combined[i][1]) - (tq3.query(0, index));
      dist[combined[i][3]] = max(d1, d2);
    } else {
      int index = get_index(combined[i][1]);
      tq1.update(index, combined[i][1] - combined[i][0]);
      tq3.update(index, combined[i][0] + combined[i][1]);
    }
  }
  sort(combined.begin(), combined.end(), homelander_sort_2);
  segt_max tq2, tq4;
  tq2.tl = unq;
  tq4.tl = unq;
  tq2.t = vector<long long>(unq << 2, -infinity);
  tq4.t = vector<long long>(unq << 2, -infinity);
  for (int i = 0; i < nh + nr; i++) {
    if (combined[i][2]) {
      int index = get_index(combined[i][1]);
      long long d1 =
          tq2.query(index, unq - 1) - (combined[i][0] + combined[i][1]);
      long long d2 = (combined[i][1] - combined[i][0]) + (tq4.query(0, index));
      dist[combined[i][3]] = max(dist[combined[i][3]], max(d1, d2));
    } else {
      int index = get_index(combined[i][1]);
      tq2.update(index, combined[i][1] + combined[i][0]);
      tq4.update(index, combined[i][0] - combined[i][1]);
    }
  }
  long long ansi = 0;
  for (int i = 0; i < nr; i++) {
    if (dist[i] < dist[ansi]) {
      ansi = i;
    }
  }
  cout << dist[ansi] << "\n" << ansi + 1 << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q = 1;
  while (q-- > 0) {
    solve();
  }
  return 0;
}

```