#include <bits/stdc++.h>
#pragma comment(linker, "/stack:20000000")
using namespace std;
template <typename T1, typename T2, typename T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple(){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <typename T1, typename T2, typename T3>
bool operator<(const triple<T1, T2, T3> &t1, const triple<T1, T2, T3> &t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else
    return t1.b < t2.b;
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  bool first = true;
  os << "[";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::map<T1, T2> &v) {
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T, typename T2>
void printarray(T a[], T2 sz, T2 beg = 0) {
  for (T2 i = beg; i < sz; i++) cout << a[i] << " ";
}
inline long long binpow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long mulmod(long long x, long long n, long long _mod) {
  long long res = 0;
  while (n) {
    if (n & 1) res = (res + x) % _mod;
    x = (x + x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(int a, int b) { return a / gcd(a, b) * (long long)b; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
inline long long lcm(long long a, long long b, long long c) {
  return lcm(lcm(a, b), c);
}
inline long long lcm(int a, int b, int c) {
  return lcm(lcm(a, b), (long long)c);
}
inline long long max(long long a, long long b) { return (a > b) ? a : b; }
inline int max(int a, int b) { return (a > b) ? a : b; }
inline double max(double a, double b) { return (a > b) ? a : b; }
inline long long max(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline double max(double a, double b, double c) { return max(a, max(b, c)); }
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
inline int min(int a, int b) { return (a < b) ? a : b; }
inline double min(double a, double b) { return (a < b) ? a : b; }
inline long long min(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline double min(double a, double b, double c) { return min(a, min(b, c)); }
inline void getar(int *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", a + ii);
  }
}
inline void getar(long long *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64", a + ii);
  }
}
struct point {
  int x, y;
  point(int xx = 0, int yy = 0) {
    x = xx;
    y = yy;
  }
};
bool operator<(const point &p1, const point &p2) { return p1.x < p2.x; }
int n;
point a[100010];
int minpref[100010];
int maxpref[100010];
int minsuf[100010];
int maxsuf[100010];
bool check(double m) {
  for (int i = 0; i < n; i++) {
    point *v =
        upper_bound(a, a + n, point(a[i].x + 2 * m + (double)5 * (1e-7), 0));
    double miny = min(minpref[i], minsuf[(v - a)]);
    double maxy = max(maxpref[i], maxsuf[(v - a)]);
    if (maxy - miny <= 2 * m) return true;
  }
  return false;
}
int main() {
  cin >> n;
  int x, y;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &x, &y);
    a[i].x = x + y;
    a[i].y = x - y;
  }
  sort(a, a + n);
  maxpref[0] = -2111111111;
  minpref[0] = 2111111111;
  maxsuf[n] = -2111111111;
  minsuf[n] = 2111111111;
  for (int i = 1; i <= n; i++) {
    minpref[i] = min(minpref[i - 1], a[i - 1].y);
    maxpref[i] = max(maxpref[i - 1], a[i - 1].y);
    minsuf[n - i] = min(minsuf[n - i + 1], a[n - i].y);
    maxsuf[n - i] = max(maxsuf[n - i + 1], a[n - i].y);
  }
  double l = 0;
  double r = max(1.0 * a[n - 1].x - a[0].x, 1.0 * maxsuf[0] - minsuf[0]) / 2;
  while (l + (double)5 * (1e-7) < r) {
    double m = (l + r) / 2;
    if (check(m)) {
      r = m;
    } else {
      l = m;
    }
  }
  cout << fixed;
  cout.precision(7);
  cout << (l + r) / 2 << endl;
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

Sereja placed n points on a plane. Now Sereja wants to place on the plane two straight lines, intersecting at a right angle, so that one of the straight lines intersect the Ox axis at an angle of 45 degrees and the maximum distance from the points to the straight lines were minimum. 

In this problem we consider the distance between points (x1, y1) and (x2, y2) equal |x1 - x2| + |y1 - y2|. The distance between the point and the straight lines is the minimum distance from the point to some point belonging to one of the lines.

Help Sereja, find the maximum distance from the points to the optimally located straight lines.

Input

The first line contains integer n (1 ≤ n ≤ 105). Next n lines contain the coordinates of the lines. The i-th line contains two integers xi, yi (|xi|, |yi| ≤ 109).

Output

In a single line print a real number — the answer to the problem. Your answer will be considered correct iff its absolute or relative error doesn't exceed 10 - 6.

Examples

Input

4
0 0
2 0
0 2
2 2


Output

0.000000000000000


Input

4
1 0
0 1
2 1
1 2


Output

1.000000000000000

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:20000000")
using namespace std;
template <typename T1, typename T2, typename T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple(){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <typename T1, typename T2, typename T3>
bool operator<(const triple<T1, T2, T3> &t1, const triple<T1, T2, T3> &t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else
    return t1.b < t2.b;
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  bool first = true;
  os << "[";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::map<T1, T2> &v) {
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T, typename T2>
void printarray(T a[], T2 sz, T2 beg = 0) {
  for (T2 i = beg; i < sz; i++) cout << a[i] << " ";
}
inline long long binpow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long mulmod(long long x, long long n, long long _mod) {
  long long res = 0;
  while (n) {
    if (n & 1) res = (res + x) % _mod;
    x = (x + x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(int a, int b) { return a / gcd(a, b) * (long long)b; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
inline long long lcm(long long a, long long b, long long c) {
  return lcm(lcm(a, b), c);
}
inline long long lcm(int a, int b, int c) {
  return lcm(lcm(a, b), (long long)c);
}
inline long long max(long long a, long long b) { return (a > b) ? a : b; }
inline int max(int a, int b) { return (a > b) ? a : b; }
inline double max(double a, double b) { return (a > b) ? a : b; }
inline long long max(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline double max(double a, double b, double c) { return max(a, max(b, c)); }
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
inline int min(int a, int b) { return (a < b) ? a : b; }
inline double min(double a, double b) { return (a < b) ? a : b; }
inline long long min(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline double min(double a, double b, double c) { return min(a, min(b, c)); }
inline void getar(int *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", a + ii);
  }
}
inline void getar(long long *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64", a + ii);
  }
}
struct point {
  int x, y;
  point(int xx = 0, int yy = 0) {
    x = xx;
    y = yy;
  }
};
bool operator<(const point &p1, const point &p2) { return p1.x < p2.x; }
int n;
point a[100010];
int minpref[100010];
int maxpref[100010];
int minsuf[100010];
int maxsuf[100010];
bool check(double m) {
  for (int i = 0; i < n; i++) {
    point *v =
        upper_bound(a, a + n, point(a[i].x + 2 * m + (double)5 * (1e-7), 0));
    double miny = min(minpref[i], minsuf[(v - a)]);
    double maxy = max(maxpref[i], maxsuf[(v - a)]);
    if (maxy - miny <= 2 * m) return true;
  }
  return false;
}
int main() {
  cin >> n;
  int x, y;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &x, &y);
    a[i].x = x + y;
    a[i].y = x - y;
  }
  sort(a, a + n);
  maxpref[0] = -2111111111;
  minpref[0] = 2111111111;
  maxsuf[n] = -2111111111;
  minsuf[n] = 2111111111;
  for (int i = 1; i <= n; i++) {
    minpref[i] = min(minpref[i - 1], a[i - 1].y);
    maxpref[i] = max(maxpref[i - 1], a[i - 1].y);
    minsuf[n - i] = min(minsuf[n - i + 1], a[n - i].y);
    maxsuf[n - i] = max(maxsuf[n - i + 1], a[n - i].y);
  }
  double l = 0;
  double r = max(1.0 * a[n - 1].x - a[0].x, 1.0 * maxsuf[0] - minsuf[0]) / 2;
  while (l + (double)5 * (1e-7) < r) {
    double m = (l + r) / 2;
    if (check(m)) {
      r = m;
    } else {
      l = m;
    }
  }
  cout << fixed;
  cout.precision(7);
  cout << (l + r) / 2 << endl;
  return 0;
}

```