#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-12 && _x < _y + 1e-12;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
pair<long double, long double> operator+(
    const pair<long double, long double>& p1,
    const pair<long double, long double>& p2) {
  return {p1.first + p2.first, p1.second + p2.second};
}
pair<long double, long double> operator-(
    const pair<long double, long double>& p1,
    const pair<long double, long double>& p2) {
  return {p1.first - p2.first, p1.second - p2.second};
}
pair<long double, long double> operator*(
    const pair<long double, long double>& tp, const long double& tk) {
  return {tp.first * tk, tp.second * tk};
}
pair<long double, long double> operator/(
    const pair<long double, long double>& tp, const long double& tk) {
  return {tp.first / tk, tp.second / tk};
}
long double operator*(const pair<long double, long double>& p1,
                      const pair<long double, long double>& p2) {
  return p1.first * p2.first + p1.second * p2.second;
}
long double operator^(const pair<long double, long double>& p1,
                      const pair<long double, long double>& p2) {
  return p1.first * p2.second - p1.second * p2.first;
}
long double norm2(const pair<long double, long double>& tp) { return tp * tp; }
long double norm(const pair<long double, long double>& tp) {
  return sqrt(norm2(tp));
}
pair<long double, long double> perp(const pair<long double, long double>& tp) {
  return {tp.second, -tp.first};
}
void scan(pair<long double, long double>& tp) {
  scanf("%LF%LF", &tp.first, &tp.second);
}
pair<long double, long double> interPnt(pair<long double, long double> p1,
                                        pair<long double, long double> p2,
                                        pair<long double, long double> q1,
                                        pair<long double, long double> q2) {
  long double f1 = (p2 - p1) ^ (q1 - p1);
  long double f2 = (p2 - p1) ^ (p1 - q2);
  long double f = (f1 + f2);
  return q1 * (f2 / f) + q2 * (f1 / f);
}
void build() {}
pair<long double, long double> a, b;
pair<pair<long double, long double>, long double> c[101010];
int n;
void init() {
  scan(a);
  scan(b);
  n = getint();
  for (int i = 0; i < n; i++) {
    scan(c[i].first);
    scanf("%LF", &c[i].second);
  }
}
pair<long double, long double> mid, dir;
inline bool okay(const pair<long double, long double>& oo,
                 const pair<long double, long double>& aa,
                 const pair<pair<long double, long double>, long double>& cc) {
  long double dira = norm(oo - aa);
  long double dirc = norm(oo - cc.first);
  if (dira < dirc) return dira + cc.second < dirc + 1e-12;
  return dirc + cc.second < dira + 1e-12;
}
long double sqr(long double xx) { return xx * xx; }
void solve() {
  mid = (a + b) * 0.5;
  dir = perp(b - a);
  vector<pair<long double, int> > vv;
  double fuck = sqrt(sqr(1e12) - norm2(a - mid));
  pair<long double, long double> umst = mid + dir * (fuck / norm(dir));
  pair<long double, long double> lmst = mid - dir * (fuck / norm(dir));
  double UU = ((umst - mid) * dir) / norm2(dir);
  double LB = ((lmst - mid) * dir) / norm2(dir);
  for (int i = 0; i < n; i++) {
    long double way = (c[i].first - a) ^ (b - a);
    if (fabs(way) < 1e-12) continue;
    pair<long double, long double> cmid = (a + c[i].first) * 0.5;
    pair<long double, long double> cen =
        interPnt(mid, mid + dir, cmid, cmid + perp(c[i].first - a));
    {
      long double br = ((umst - cen) * dir) / norm2(dir);
      long double bl = 0, ba = 0;
      for (int k = 0; k < 120; k++) {
        long double bmid = (bl + br) * 0.5;
        pair<long double, long double> cand = cen + dir * bmid;
        if (okay(cand, a, c[i]))
          ba = bmid, br = bmid;
        else
          bl = bmid;
      }
      pair<long double, long double> rp = cen + dir * ba;
      long double vl = ((rp - mid) * dir) / norm2(dir);
      vv.push_back({vl - 1e-12, +1});
      vv.push_back({UU, -1});
    }
    {
      long double br = ((lmst - cen) * (dir * -1)) / norm2(dir);
      long double bl = 0, ba = 0;
      for (int k = 0; k < 120; k++) {
        long double bmid = (bl + br) * 0.5;
        pair<long double, long double> cand = cen - dir * bmid;
        if (okay(cand, a, c[i]))
          ba = bmid, br = bmid;
        else
          bl = bmid;
      }
      pair<long double, long double> rp = cen - dir * ba;
      long double vl = ((rp - mid) * dir) / norm2(dir);
      vv.push_back({LB, +1});
      vv.push_back({vl + 1e-12, -1});
    }
  }
  sort(vv.begin(), vv.end());
  long double ans = 1e12;
  if (vv.empty()) ans = min(ans, norm(mid - a));
  int ps = 0;
  for (size_t i = 0; i + 1 < vv.size(); i++) {
    ps += vv[i].second;
    if (ps == n) {
      long double lb = vv[i].first;
      long double rb = vv[i + 1].first;
      ans = min(ans, norm((mid + dir * lb) - a));
      ans = min(ans, norm((mid + dir * rb) - a));
      if (lb < 0 and 0 < rb) ans = min(ans, norm(mid - a));
    }
  }
  printf("%.12f\n", (double)ans);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

### 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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-12 && _x < _y + 1e-12;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
pair<long double, long double> operator+(
    const pair<long double, long double>& p1,
    const pair<long double, long double>& p2) {
  return {p1.first + p2.first, p1.second + p2.second};
}
pair<long double, long double> operator-(
    const pair<long double, long double>& p1,
    const pair<long double, long double>& p2) {
  return {p1.first - p2.first, p1.second - p2.second};
}
pair<long double, long double> operator*(
    const pair<long double, long double>& tp, const long double& tk) {
  return {tp.first * tk, tp.second * tk};
}
pair<long double, long double> operator/(
    const pair<long double, long double>& tp, const long double& tk) {
  return {tp.first / tk, tp.second / tk};
}
long double operator*(const pair<long double, long double>& p1,
                      const pair<long double, long double>& p2) {
  return p1.first * p2.first + p1.second * p2.second;
}
long double operator^(const pair<long double, long double>& p1,
                      const pair<long double, long double>& p2) {
  return p1.first * p2.second - p1.second * p2.first;
}
long double norm2(const pair<long double, long double>& tp) { return tp * tp; }
long double norm(const pair<long double, long double>& tp) {
  return sqrt(norm2(tp));
}
pair<long double, long double> perp(const pair<long double, long double>& tp) {
  return {tp.second, -tp.first};
}
void scan(pair<long double, long double>& tp) {
  scanf("%LF%LF", &tp.first, &tp.second);
}
pair<long double, long double> interPnt(pair<long double, long double> p1,
                                        pair<long double, long double> p2,
                                        pair<long double, long double> q1,
                                        pair<long double, long double> q2) {
  long double f1 = (p2 - p1) ^ (q1 - p1);
  long double f2 = (p2 - p1) ^ (p1 - q2);
  long double f = (f1 + f2);
  return q1 * (f2 / f) + q2 * (f1 / f);
}
void build() {}
pair<long double, long double> a, b;
pair<pair<long double, long double>, long double> c[101010];
int n;
void init() {
  scan(a);
  scan(b);
  n = getint();
  for (int i = 0; i < n; i++) {
    scan(c[i].first);
    scanf("%LF", &c[i].second);
  }
}
pair<long double, long double> mid, dir;
inline bool okay(const pair<long double, long double>& oo,
                 const pair<long double, long double>& aa,
                 const pair<pair<long double, long double>, long double>& cc) {
  long double dira = norm(oo - aa);
  long double dirc = norm(oo - cc.first);
  if (dira < dirc) return dira + cc.second < dirc + 1e-12;
  return dirc + cc.second < dira + 1e-12;
}
long double sqr(long double xx) { return xx * xx; }
void solve() {
  mid = (a + b) * 0.5;
  dir = perp(b - a);
  vector<pair<long double, int> > vv;
  double fuck = sqrt(sqr(1e12) - norm2(a - mid));
  pair<long double, long double> umst = mid + dir * (fuck / norm(dir));
  pair<long double, long double> lmst = mid - dir * (fuck / norm(dir));
  double UU = ((umst - mid) * dir) / norm2(dir);
  double LB = ((lmst - mid) * dir) / norm2(dir);
  for (int i = 0; i < n; i++) {
    long double way = (c[i].first - a) ^ (b - a);
    if (fabs(way) < 1e-12) continue;
    pair<long double, long double> cmid = (a + c[i].first) * 0.5;
    pair<long double, long double> cen =
        interPnt(mid, mid + dir, cmid, cmid + perp(c[i].first - a));
    {
      long double br = ((umst - cen) * dir) / norm2(dir);
      long double bl = 0, ba = 0;
      for (int k = 0; k < 120; k++) {
        long double bmid = (bl + br) * 0.5;
        pair<long double, long double> cand = cen + dir * bmid;
        if (okay(cand, a, c[i]))
          ba = bmid, br = bmid;
        else
          bl = bmid;
      }
      pair<long double, long double> rp = cen + dir * ba;
      long double vl = ((rp - mid) * dir) / norm2(dir);
      vv.push_back({vl - 1e-12, +1});
      vv.push_back({UU, -1});
    }
    {
      long double br = ((lmst - cen) * (dir * -1)) / norm2(dir);
      long double bl = 0, ba = 0;
      for (int k = 0; k < 120; k++) {
        long double bmid = (bl + br) * 0.5;
        pair<long double, long double> cand = cen - dir * bmid;
        if (okay(cand, a, c[i]))
          ba = bmid, br = bmid;
        else
          bl = bmid;
      }
      pair<long double, long double> rp = cen - dir * ba;
      long double vl = ((rp - mid) * dir) / norm2(dir);
      vv.push_back({LB, +1});
      vv.push_back({vl + 1e-12, -1});
    }
  }
  sort(vv.begin(), vv.end());
  long double ans = 1e12;
  if (vv.empty()) ans = min(ans, norm(mid - a));
  int ps = 0;
  for (size_t i = 0; i + 1 < vv.size(); i++) {
    ps += vv[i].second;
    if (ps == n) {
      long double lb = vv[i].first;
      long double rb = vv[i + 1].first;
      ans = min(ans, norm((mid + dir * lb) - a));
      ans = min(ans, norm((mid + dir * rb) - a));
      if (lb < 0 and 0 < rb) ans = min(ans, norm(mid - a));
    }
  }
  printf("%.12f\n", (double)ans);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

```