#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
const double PI = 3.1415926535;
inline int sgn(double x) { return (x > eps) - (x < -eps); }
struct Point {
  double x, y;
  Point() : x(0), y(0) {}
  Point(double _x, double _y) : x(_x), y(_y) {}
  void set(double _x, double _y) {
    this->x = _x;
    this->y = _y;
  }
  Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
  Point operator*(const double &q) const { return Point(x * q, y * q); }
  Point operator/(const double &q) const { return Point(x / q, y / q); }
  bool operator==(const Point &p) const {
    return fabs(p.x - x) < eps && fabs(p.y - y) < eps;
  }
  bool operator!=(const Point &p) const { return ((*this) == p) == false; }
  friend bool operator<(const Point &p1, const Point &p2) {
    return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x);
  }
  void read() { cin >> this->x >> this->y; }
  void print() const { cout << "Point" << x << "," << y << endl; }
};
inline double Dot(const Point &p1, const Point &p2) {
  return p1.x * p2.x + p1.y * p2.y;
}
inline double Cross(const Point &p1, const Point &p2) {
  return p1.x * p2.y - p2.x * p1.y;
}
inline double Length2(const Point &p1) { return p1.x * p1.x + p1.y * p1.y; }
inline double Length(const Point &p) { return sqrt(Length2(p)); }
inline double Angle(const Point &p) { return atan2(p.y, p.x); }
void LineIntersect(const Point &p1, const Point &p2, const Point &q1,
                   const Point &q2, Point &ret) {
  double ratio = Cross(p1 - q1, p1 - p2) / Cross(q2 - q1, p1 - p2);
  ret = q1 + (q2 - q1) * ratio;
}
bool PointOnSegment(const Point &p, const Point &seg1, const Point &seg2) {
  return sgn(Cross(seg1 - p, seg2 - p)) == 0 &&
         sgn(Dot(seg1 - p, seg2 - p)) <= 0;
}
bool SegmentIntersect(const Point &p1, const Point &p2, const Point &q1,
                      const Point &q2) {
  return max(p1.x, p2.x) >= min(q1.x, q2.x) &&
         min(p1.x, p2.x) <= max(q1.x, q2.x) &&
         max(p1.y, p2.y) >= min(q1.y, q2.y) &&
         min(p1.y, p2.y) <= max(q1.y, q2.y) &&
         Cross(q1 - p1, q2 - p1) * Cross(q1 - p2, q2 - p2) <= 0 &&
         Cross(p1 - q1, p2 - q1) * Cross(p1 - q2, p2 - q2) <= 0;
}
int ConvexHull(Point *p, int n, Point *ch) {
  sort(p, p + n);
  int m = 0;
  for (int i = 0; i < n; i++) {
    while (m > 1 && sgn(Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) < 0)
      m--;
    ch[m++] = p[i];
  }
  int k = m;
  for (int i = n - 2; i >= 0; i--) {
    while (m > k && sgn(Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) < 0)
      m--;
    ch[m++] = p[i];
  }
  if (n > 1) m--;
  return m;
}
bool SegmentIntersect(const Point &p1, const Point &p2, const Point &q1,
                      const Point &q2, Point &ret) {
  if (!SegmentIntersect(p1, p2, q1, q2)) return false;
  LineIntersect(p1, p2, q1, q2, ret);
  return true;
}
void rotate(const Point &v1, Point &ret, double theta) {
  ret.x = v1.x * cos(theta) - v1.y * sin(theta);
  ret.y = v1.x * sin(theta) + v1.y * sin(theta);
}
inline double Abs(double x) { return sgn(x) > 0 ? x : -x; }
double distPointtoLine(const Point &p, const Point &l1, const Point &l2) {
  Point v = l2 - l1;
  Point pl = p - l1;
  return fabs(Cross(v, pl) / Length(v));
}
Point rotate90(const Point &p) { return Point(p.y, -p.x); }
double distPointtoSeg(const Point &p, const Point &s1, const Point &s2) {
  Point toLine =
      p + rotate90(s2 - s1) * distPointtoLine(p, s1, s2) / Length(s1 - s2);
  if (sgn(Dot(toLine - s1, toLine - s2)) <= 0) {
    return fabs(distPointtoLine(p, s1, s2));
  } else {
    return min(Length(p - s1), Length(p - s2));
  }
}
double distSegtoSeg(const Point &s1, const Point &s2, const Point &q1,
                    const Point &q2) {
  return min(min(distPointtoSeg(s1, q1, q2), distPointtoSeg(s2, q1, q2)),
             min(distPointtoSeg(q1, s1, s2), distPointtoSeg(q2, s1, s2)));
}
inline int inCircle(const Point &p, const Point &c, double r) {
  double len = Length(p - c);
  return sgn(r - len);
}
int LineCircleIntersect(const Point &l1, const Point &l2, const Point &c,
                        const double &r, vector<Point> &ret) {
  ret.clear();
  double dist = distPointtoLine(c, l1, l2);
  if (sgn(dist - r) > 0) return 0;
  Point v = l2 - l1;
  Point cross = l1 + v * Dot(v, c - l1) / Length2(v);
  if (sgn(dist - r) == 0) {
    ret.push_back(cross);
    return 1;
  }
  double len = sqrt(r * r - dist * dist);
  ret.push_back(cross - v / Length(v) * len);
  ret.push_back(cross + v / Length(v) * len);
  return 2;
}
int SegmentCircleIntersect(const Point &s1, const Point &s2, const Point &c,
                           const double &r, vector<Point> &ret) {
  vector<Point> tmp;
  int cnt = LineCircleIntersect(s1, s2, c, r, tmp);
  ret.clear();
  for (int i = 0; i < cnt; i++) {
    if (PointOnSegment(tmp[i], s1, s2)) ret.push_back(tmp[i]);
  }
  return ret.size();
}
double AngleBetweenVector(const Point &p1, const Point &p2) {
  return acos(Dot(p1, p2) / Length(p1) / Length(p2)) * sgn(Cross(p1, p2));
}
double Circle_Triangle_Intersection(const Point &c, double r, const Point &a,
                                    const Point &b) {
  bool ainc = inCircle(a, c, r) > 0;
  bool binc = inCircle(b, c, r) > 0;
  if (PointOnSegment(c, a, b)) return 0;
  if (ainc && binc) {
    return Cross(a - c, b - c) / 2;
  } else if (!ainc && binc) {
    vector<Point> interAB;
    SegmentCircleIntersect(b, a, c, r, interAB);
    double angle = AngleBetweenVector(a - c, interAB[0] - c);
    return Cross(interAB[0] - c, b - c) / 2 + angle / 2 * r * r;
  } else if (ainc && !binc) {
    vector<Point> interAB;
    SegmentCircleIntersect(b, a, c, r, interAB);
    double angle = AngleBetweenVector(interAB[0] - c, b - c);
    return Cross(a - c, interAB[0] - c) / 2 + angle / 2 * r * r;
  } else {
    vector<Point> interAB;
    int cnt = SegmentCircleIntersect(a, b, c, r, interAB);
    if (cnt <= 1) {
      double angle = AngleBetweenVector(a - c, b - c);
      return angle / 2 * r * r;
    } else {
      double angle = AngleBetweenVector(a - c, interAB[0] - c);
      double angle2 = AngleBetweenVector(interAB[1] - c, b - c);
      return Cross(interAB[0] - c, interAB[1] - c) / 2 +
             (angle + angle2) / 2 * r * r;
    }
  }
}
double Circle_Polygon_Intersection(const Point &c, double r,
                                   vector<Point> &polygon) {
  double ret = 0;
  int n = polygon.size();
  for (int i = 0; i < n; i++) {
    ret += Circle_Triangle_Intersection(c, r, polygon[i], polygon[(i + 1) % n]);
  }
  return ret;
}
typedef double (*pfunc)(const Point &);
double gradient_decent(const Point &initial_pos, int max_iter, double step_size,
                       double learning_rate, pfunc function) {
  Point cur_pos = initial_pos;
  Point mx_pos;
  double cur_val, last_val;
  int iter = 0;
  cur_val = function(cur_pos);
  do {
    last_val = cur_val;
    double mx_val = cur_val;
    bool flag = false;
    for (int i = 0; i < 30; i++) {
      double angle = (1 + rand() % 1000) / 1000.0 * 2 * PI;
      Point tmp_pos(cos(angle), sin(angle));
      double tmp_val = function(cur_pos + tmp_pos * step_size);
      if (sgn(tmp_val - mx_val) > 0) {
        mx_val = tmp_val;
        mx_pos = cur_pos + tmp_pos * step_size;
        flag = true;
      }
    }
    if (flag) {
      cur_pos = mx_pos;
      cur_val = mx_val;
    } else if (!flag)
      step_size *= learning_rate;
  } while (++iter <= max_iter && step_size > 1e-6);
  return last_val;
}
Point angular_bisector(const Point &p, const Point &a, const Point &b) {
  return (a - p) / Length(a - p) + (b - p) / Length(b - p);
}
struct Circle {
  Point c;
  double r;
  void read() {
    c.read();
    cin >> r;
  }
};
Point x, y, o, k;
double dist2;
int n;
Circle c;
vector<pair<double, double> > pos, neg;
double work(double d, double target) {
  return sqrt(dist2 + d * d) - Length(c.c - o + k * d) - target;
}
double bisection(double target) {
  double b = -1e12, e = 1e12;
  int sig = sgn(work(b, target));
  for (int i = 1; i <= 200; i++) {
    double m = (b + e) / 2;
    double d = work(m, target);
    if (sgn(d) * sig > 0)
      b = m;
    else
      e = m;
  }
  return e;
}
bool cmp(const pair<double, double> &p, const pair<double, double> &q) {
  return sgn(q.second - p.second) > 0;
}
int main() {
  x.read();
  y.read();
  k = Point(x.y - y.y, y.x - x.x);
  k = k / Length(k);
  dist2 = Length2((x - y) / 2);
  o = (x + y) / 2;
  pos.clear();
  neg.clear();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    c.read();
    pair<double, double> tmp = {bisection(c.r), bisection(-c.r)};
    if (sgn(tmp.first - tmp.second) > 0) swap(tmp.first, tmp.second);
    if (sgn(tmp.first) < 0 && sgn(tmp.second) > 0) {
      neg.push_back({tmp.first, 0});
      pos.push_back({0, tmp.second});
    } else {
      if (sgn(tmp.first) > 0)
        pos.push_back(tmp);
      else
        neg.push_back(tmp);
    }
  }
  sort(pos.begin(), pos.end());
  sort(neg.begin(), neg.end(), cmp);
  double ans = 1e12;
  double left = 0, right = 0;
  for (int i = 0; i < pos.size(); i++) {
    if (sgn(pos[i].first - left) > 0) break;
    left = max(left, pos[i].second);
  }
  ans = min(ans, fabs(left));
  right = left = 0;
  for (int i = (int)neg.size() - 1; i >= 0; i--) {
    if (sgn(neg[i].second - right) < 0) break;
    right = min(right, neg[i].first);
  }
  ans = min(ans, fabs(right));
  cout << fixed << setprecision(10) << sqrt(ans * ans + dist2) << endl;
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

Masha's little brother draw two points on a sheet of paper. After that, he draws some circles and gave the sheet to his sister. 

Masha has just returned from geometry lesson so she instantly noticed some interesting facts about brother's drawing.

At first, the line going through two points, that brother drew, doesn't intersect or touch any circle.

Also, no two circles intersect or touch, and there is no pair of circles such that one circle is located inside another.

Moreover, for each circle, Masha drew a square of the minimal area with sides parallel axis such that this circle is located inside the square and noticed that there is no two squares intersect or touch and there is no pair of squares such that one square is located inside other.

Now Masha wants to draw circle of minimal possible radius such that it goes through two points that brother drew and doesn't intersect any other circle, but other circles can touch Masha's circle and can be located inside it.

It's guaranteed, that answer won't exceed 1012. It should be held for hacks as well.

Input

First line contains four integers x1, y1, x2, y2 ( - 105 ≤ x1, y1, x2, y2 ≤ 105) — coordinates of points that brother drew. First point has coordinates (x1, y1) and second point has coordinates (x2, y2). These two points are different.

The second line contains single integer n (1 ≤ n ≤ 105) — the number of circles that brother drew.

Next n lines contains descriptions of circles. Each line contains three integers xi, yi, ri ( - 105 ≤ xi, yi ≤ 105, 1 ≤ ri ≤ 105) describing circle with center (xi, yi) and radius ri.

Output

Output smallest real number, that it's possible to draw a circle with such radius through given points in such a way that it doesn't intersect other circles.

The output is considered correct if it has a relative or absolute error of at most 10 - 4.

Examples

Input

2 4 7 13
3
3 0 1
12 4 2
-4 14 2


Output

5.1478150705

Input

-2 3 10 -10
2
7 0 3
-5 -5 2


Output

9.1481831923

Note

<image> <image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
const double PI = 3.1415926535;
inline int sgn(double x) { return (x > eps) - (x < -eps); }
struct Point {
  double x, y;
  Point() : x(0), y(0) {}
  Point(double _x, double _y) : x(_x), y(_y) {}
  void set(double _x, double _y) {
    this->x = _x;
    this->y = _y;
  }
  Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
  Point operator*(const double &q) const { return Point(x * q, y * q); }
  Point operator/(const double &q) const { return Point(x / q, y / q); }
  bool operator==(const Point &p) const {
    return fabs(p.x - x) < eps && fabs(p.y - y) < eps;
  }
  bool operator!=(const Point &p) const { return ((*this) == p) == false; }
  friend bool operator<(const Point &p1, const Point &p2) {
    return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x);
  }
  void read() { cin >> this->x >> this->y; }
  void print() const { cout << "Point" << x << "," << y << endl; }
};
inline double Dot(const Point &p1, const Point &p2) {
  return p1.x * p2.x + p1.y * p2.y;
}
inline double Cross(const Point &p1, const Point &p2) {
  return p1.x * p2.y - p2.x * p1.y;
}
inline double Length2(const Point &p1) { return p1.x * p1.x + p1.y * p1.y; }
inline double Length(const Point &p) { return sqrt(Length2(p)); }
inline double Angle(const Point &p) { return atan2(p.y, p.x); }
void LineIntersect(const Point &p1, const Point &p2, const Point &q1,
                   const Point &q2, Point &ret) {
  double ratio = Cross(p1 - q1, p1 - p2) / Cross(q2 - q1, p1 - p2);
  ret = q1 + (q2 - q1) * ratio;
}
bool PointOnSegment(const Point &p, const Point &seg1, const Point &seg2) {
  return sgn(Cross(seg1 - p, seg2 - p)) == 0 &&
         sgn(Dot(seg1 - p, seg2 - p)) <= 0;
}
bool SegmentIntersect(const Point &p1, const Point &p2, const Point &q1,
                      const Point &q2) {
  return max(p1.x, p2.x) >= min(q1.x, q2.x) &&
         min(p1.x, p2.x) <= max(q1.x, q2.x) &&
         max(p1.y, p2.y) >= min(q1.y, q2.y) &&
         min(p1.y, p2.y) <= max(q1.y, q2.y) &&
         Cross(q1 - p1, q2 - p1) * Cross(q1 - p2, q2 - p2) <= 0 &&
         Cross(p1 - q1, p2 - q1) * Cross(p1 - q2, p2 - q2) <= 0;
}
int ConvexHull(Point *p, int n, Point *ch) {
  sort(p, p + n);
  int m = 0;
  for (int i = 0; i < n; i++) {
    while (m > 1 && sgn(Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) < 0)
      m--;
    ch[m++] = p[i];
  }
  int k = m;
  for (int i = n - 2; i >= 0; i--) {
    while (m > k && sgn(Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) < 0)
      m--;
    ch[m++] = p[i];
  }
  if (n > 1) m--;
  return m;
}
bool SegmentIntersect(const Point &p1, const Point &p2, const Point &q1,
                      const Point &q2, Point &ret) {
  if (!SegmentIntersect(p1, p2, q1, q2)) return false;
  LineIntersect(p1, p2, q1, q2, ret);
  return true;
}
void rotate(const Point &v1, Point &ret, double theta) {
  ret.x = v1.x * cos(theta) - v1.y * sin(theta);
  ret.y = v1.x * sin(theta) + v1.y * sin(theta);
}
inline double Abs(double x) { return sgn(x) > 0 ? x : -x; }
double distPointtoLine(const Point &p, const Point &l1, const Point &l2) {
  Point v = l2 - l1;
  Point pl = p - l1;
  return fabs(Cross(v, pl) / Length(v));
}
Point rotate90(const Point &p) { return Point(p.y, -p.x); }
double distPointtoSeg(const Point &p, const Point &s1, const Point &s2) {
  Point toLine =
      p + rotate90(s2 - s1) * distPointtoLine(p, s1, s2) / Length(s1 - s2);
  if (sgn(Dot(toLine - s1, toLine - s2)) <= 0) {
    return fabs(distPointtoLine(p, s1, s2));
  } else {
    return min(Length(p - s1), Length(p - s2));
  }
}
double distSegtoSeg(const Point &s1, const Point &s2, const Point &q1,
                    const Point &q2) {
  return min(min(distPointtoSeg(s1, q1, q2), distPointtoSeg(s2, q1, q2)),
             min(distPointtoSeg(q1, s1, s2), distPointtoSeg(q2, s1, s2)));
}
inline int inCircle(const Point &p, const Point &c, double r) {
  double len = Length(p - c);
  return sgn(r - len);
}
int LineCircleIntersect(const Point &l1, const Point &l2, const Point &c,
                        const double &r, vector<Point> &ret) {
  ret.clear();
  double dist = distPointtoLine(c, l1, l2);
  if (sgn(dist - r) > 0) return 0;
  Point v = l2 - l1;
  Point cross = l1 + v * Dot(v, c - l1) / Length2(v);
  if (sgn(dist - r) == 0) {
    ret.push_back(cross);
    return 1;
  }
  double len = sqrt(r * r - dist * dist);
  ret.push_back(cross - v / Length(v) * len);
  ret.push_back(cross + v / Length(v) * len);
  return 2;
}
int SegmentCircleIntersect(const Point &s1, const Point &s2, const Point &c,
                           const double &r, vector<Point> &ret) {
  vector<Point> tmp;
  int cnt = LineCircleIntersect(s1, s2, c, r, tmp);
  ret.clear();
  for (int i = 0; i < cnt; i++) {
    if (PointOnSegment(tmp[i], s1, s2)) ret.push_back(tmp[i]);
  }
  return ret.size();
}
double AngleBetweenVector(const Point &p1, const Point &p2) {
  return acos(Dot(p1, p2) / Length(p1) / Length(p2)) * sgn(Cross(p1, p2));
}
double Circle_Triangle_Intersection(const Point &c, double r, const Point &a,
                                    const Point &b) {
  bool ainc = inCircle(a, c, r) > 0;
  bool binc = inCircle(b, c, r) > 0;
  if (PointOnSegment(c, a, b)) return 0;
  if (ainc && binc) {
    return Cross(a - c, b - c) / 2;
  } else if (!ainc && binc) {
    vector<Point> interAB;
    SegmentCircleIntersect(b, a, c, r, interAB);
    double angle = AngleBetweenVector(a - c, interAB[0] - c);
    return Cross(interAB[0] - c, b - c) / 2 + angle / 2 * r * r;
  } else if (ainc && !binc) {
    vector<Point> interAB;
    SegmentCircleIntersect(b, a, c, r, interAB);
    double angle = AngleBetweenVector(interAB[0] - c, b - c);
    return Cross(a - c, interAB[0] - c) / 2 + angle / 2 * r * r;
  } else {
    vector<Point> interAB;
    int cnt = SegmentCircleIntersect(a, b, c, r, interAB);
    if (cnt <= 1) {
      double angle = AngleBetweenVector(a - c, b - c);
      return angle / 2 * r * r;
    } else {
      double angle = AngleBetweenVector(a - c, interAB[0] - c);
      double angle2 = AngleBetweenVector(interAB[1] - c, b - c);
      return Cross(interAB[0] - c, interAB[1] - c) / 2 +
             (angle + angle2) / 2 * r * r;
    }
  }
}
double Circle_Polygon_Intersection(const Point &c, double r,
                                   vector<Point> &polygon) {
  double ret = 0;
  int n = polygon.size();
  for (int i = 0; i < n; i++) {
    ret += Circle_Triangle_Intersection(c, r, polygon[i], polygon[(i + 1) % n]);
  }
  return ret;
}
typedef double (*pfunc)(const Point &);
double gradient_decent(const Point &initial_pos, int max_iter, double step_size,
                       double learning_rate, pfunc function) {
  Point cur_pos = initial_pos;
  Point mx_pos;
  double cur_val, last_val;
  int iter = 0;
  cur_val = function(cur_pos);
  do {
    last_val = cur_val;
    double mx_val = cur_val;
    bool flag = false;
    for (int i = 0; i < 30; i++) {
      double angle = (1 + rand() % 1000) / 1000.0 * 2 * PI;
      Point tmp_pos(cos(angle), sin(angle));
      double tmp_val = function(cur_pos + tmp_pos * step_size);
      if (sgn(tmp_val - mx_val) > 0) {
        mx_val = tmp_val;
        mx_pos = cur_pos + tmp_pos * step_size;
        flag = true;
      }
    }
    if (flag) {
      cur_pos = mx_pos;
      cur_val = mx_val;
    } else if (!flag)
      step_size *= learning_rate;
  } while (++iter <= max_iter && step_size > 1e-6);
  return last_val;
}
Point angular_bisector(const Point &p, const Point &a, const Point &b) {
  return (a - p) / Length(a - p) + (b - p) / Length(b - p);
}
struct Circle {
  Point c;
  double r;
  void read() {
    c.read();
    cin >> r;
  }
};
Point x, y, o, k;
double dist2;
int n;
Circle c;
vector<pair<double, double> > pos, neg;
double work(double d, double target) {
  return sqrt(dist2 + d * d) - Length(c.c - o + k * d) - target;
}
double bisection(double target) {
  double b = -1e12, e = 1e12;
  int sig = sgn(work(b, target));
  for (int i = 1; i <= 200; i++) {
    double m = (b + e) / 2;
    double d = work(m, target);
    if (sgn(d) * sig > 0)
      b = m;
    else
      e = m;
  }
  return e;
}
bool cmp(const pair<double, double> &p, const pair<double, double> &q) {
  return sgn(q.second - p.second) > 0;
}
int main() {
  x.read();
  y.read();
  k = Point(x.y - y.y, y.x - x.x);
  k = k / Length(k);
  dist2 = Length2((x - y) / 2);
  o = (x + y) / 2;
  pos.clear();
  neg.clear();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    c.read();
    pair<double, double> tmp = {bisection(c.r), bisection(-c.r)};
    if (sgn(tmp.first - tmp.second) > 0) swap(tmp.first, tmp.second);
    if (sgn(tmp.first) < 0 && sgn(tmp.second) > 0) {
      neg.push_back({tmp.first, 0});
      pos.push_back({0, tmp.second});
    } else {
      if (sgn(tmp.first) > 0)
        pos.push_back(tmp);
      else
        neg.push_back(tmp);
    }
  }
  sort(pos.begin(), pos.end());
  sort(neg.begin(), neg.end(), cmp);
  double ans = 1e12;
  double left = 0, right = 0;
  for (int i = 0; i < pos.size(); i++) {
    if (sgn(pos[i].first - left) > 0) break;
    left = max(left, pos[i].second);
  }
  ans = min(ans, fabs(left));
  right = left = 0;
  for (int i = (int)neg.size() - 1; i >= 0; i--) {
    if (sgn(neg[i].second - right) < 0) break;
    right = min(right, neg[i].first);
  }
  ans = min(ans, fabs(right));
  cout << fixed << setprecision(10) << sqrt(ans * ans + dist2) << endl;
  return 0;
}

```