#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() { return abs((int)mt()); }
struct point_t {
  double x, y;
  point_t() : x(0), y(0) {}
  point_t(double x, double y) : x(x), y(y) {}
  point_t(const point_t& p) : x(p.x), y(p.y) {}
  int operator<(const point_t& rhs) const {
    return make_pair(y, x) < make_pair(rhs.y, rhs.x);
  }
  int operator==(const point_t& rhs) const {
    return make_pair(y, x) == make_pair(rhs.y, rhs.x);
  }
  point_t operator+(const point_t& p) const {
    return point_t(x + p.x, y + p.y);
  }
  point_t operator-(const point_t& p) const {
    return point_t(x - p.x, y - p.y);
  }
  point_t operator*(double c) const { return point_t(x * c, y * c); }
  point_t operator/(double c) const { return point_t(x / c, y / c); }
};
double cross(point_t p, point_t q) { return p.x * q.y - p.y * q.x; }
double area(point_t a, point_t b, point_t c) {
  return fabs(cross(a, b) + cross(b, c) + cross(c, a)) / 2;
}
double area2(point_t a, point_t b, point_t c) {
  return cross(a, b) + cross(b, c) + cross(c, a);
}
double dot(point_t p, point_t q) { return p.x * q.x + p.y * q.y; }
double dist(point_t p, point_t q) { return sqrt(dot(p - q, p - q)); }
double dist2(point_t p, point_t q) { return dot(p - q, p - q); }
point_t RotateCCW90(point_t p) { return point_t(-p.y, p.x); }
point_t RotateCW90(point_t p) { return point_t(p.y, -p.x); }
point_t RotateCCW(point_t p, double t) {
  return point_t(p.x * cos(t) - p.y * sin(t), p.x * sin(t) + p.y * cos(t));
}
int sign(double x) { return x < -1e-9 ? -1 : x > 1e-9; }
int sign(double x, double y) { return sign(x - y); }
ostream& operator<<(ostream& os, const point_t& p) {
  os << "(" << p.x << "," << p.y << ")";
  return os;
}
point_t ProjectPointLine(point_t a, point_t b, point_t c) {
  return a + (b - a) * dot(c - a, b - a) / dot(b - a, b - a);
}
double DistancePointLine(point_t a, point_t b, point_t c) {
  return dist(c, ProjectPointLine(a, b, c));
}
point_t ComputeLineIntersection(point_t a, point_t b, point_t c, point_t d) {
  b = b - a;
  d = c - d;
  c = c - a;
  return a + b * cross(c, d) / cross(b, d);
}
struct Line {
  point_t l, r;
  Line() {}
  Line(point_t l, point_t r) : l(l), r(r) {}
  Line(const Line& rhs) : l(rhs.l), r(rhs.r) {}
};
Line Bisector(point_t a, point_t b) {
  point_t c = (a + b) / 2;
  return Line(c, c + RotateCCW90(b - c));
}
struct Circle {
  point_t cen;
  double rad;
  Circle() : rad(0) {}
  Circle(point_t cen, double rad) : cen(cen), rad(rad) {}
  Circle(const Circle& rhs) : cen(rhs.cen), rad(rhs.rad) {}
  int operator<(const Circle& rhs) const { return rad < rhs.rad; }
};
Circle CircumCircle(point_t a, point_t b, point_t c) {
  if (sign(cross(a - c, b - c)) == 0) {
    Circle res = Circle((a + b) / 2, dist(a, b) / 2);
    res = max(res, Circle((b + c) / 2, dist(b, c) / 2));
    res = max(res, Circle((c + a) / 2, dist(c, a) / 2));
    return res;
  }
  Line ln1 = Bisector(a, b);
  Line ln2 = Bisector(b, c);
  point_t cen = ComputeLineIntersection(ln1.l, ln1.r, ln2.l, ln2.r);
  return Circle(cen, dist(cen, a));
}
void chemthan() {
  int k, n;
  cin >> k >> n;
  vector<point_t> pts(n * k);
  for (point_t& p : pts) cin >> p.x >> p.y;
  vector<Circle> res;
  auto calc = [&](Circle c) {
    int cnt = 0;
    for (int i = (0); i < (int((pts).size())); ++i) {
      double d = dist(c.cen, pts[i]);
      if (abs(d - c.rad) < 5e4) {
        cnt++;
      }
    }
    if (!cnt) return 1e9;
    return abs(cnt - (double)int((pts).size()) / (k - int((res).size())));
  };
  for (int it = (0); it < (k); ++it) {
    vector<pair<double, Circle>> candidates;
    for (int it = (0); it < (1000); ++it) {
      int u = mrand() % int((pts).size());
      int v = mrand() % int((pts).size());
      int w = mrand() % int((pts).size());
      if (5e4 < dist(pts[u], pts[v]) && 5e4 < dist(pts[v], pts[w]) &&
          5e4 < dist(pts[w], pts[u])) {
        Circle c = CircumCircle(pts[u], pts[v], pts[w]);
        candidates.push_back(make_pair(calc(c), c));
      }
    }
    sort((candidates).begin(), (candidates).end());
    Circle tmp;
    for (auto e : candidates) {
      Circle c = e.second;
      int found = 0;
      for (Circle cc : res) {
        double d = dist(c.cen, cc.cen);
        if (d < 0.1 * 600000) {
          found = 1;
          break;
        }
      }
      if (!found) {
        tmp = c;
        break;
      }
    }
    res.push_back(tmp);
    for (int i = (int((pts).size())) - 1; i >= (0); --i) {
      double d = dist(pts[i], res.back().cen);
      if (abs(d - res.back().rad) < 5e4) {
        pts.erase(pts.begin() + i);
      }
    }
    cerr << "["
         << "sz(pts)"
         << ": " << (int((pts).size())) << "] ";
    cerr << "\n";
    ;
  }
  assert(int((res).size()) == k);
  for (Circle c : res) {
    cout << fixed << setprecision(9) << c.cen.x << " " << c.cen.y << " "
         << c.rad << "\n";
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

The Cybermen have again outwitted the Daleks! Unfortunately, this time the Daleks decided to abandon these tasks altogether, which means the Doctor has to deal with them.

The Doctor can handle the Daleks on his own, but Heidi now has to make sure that the Cybermen are kept busy with this next task.

There are k rings on a plane. For each ring, n points are uniformly sampled with a small random noise. The task is to recover the rings given only the noisy samples.

The rings and the samples are generated as follows. The center of a ring is uniformly sampled from a disk of radius 1 000 000 centered at the origin, and the radius of the ring is uniformly sampled from [250 000, 750 000]. Let R be a ring with center (x, y) and radius r. To sample a point from R, an angle θ is uniformly sampled from [0, 2π] and a distance d is uniformly sampled from [0.9r, 1.1r]. The coordinates of the sampled point are then (x+dcos(θ), y+dsin(θ)) rounded to the closest integers.

The distance between rings is measured by their Hausdorff distance. In our case, the distance between two rings R_1, R_2 can be written as follow. Let d be the distance between the two centers and r_1, r_2 be the radii. Then the distance is $$$dist(R_1, R_2)=max(min(d_{--}, d_{-+}),min(d_{+-}, d_{++}), min(d_{--}, d_{+-}), min(d_{-+}, d_{++})), where d_{++}=|d+r_1+r_2|, d_{+-}=|d+r_1-r_2|, d_{-+}=|d-r_1+r_2|, d_{--}=|d-r_1-r_2|$$$.

We say that a ring R_0 is recovered if one of the rings R in the output has Hausdorff distance less than 100 000 from R_0. 

An output is accepted if all the rings are recovered. It is guaranteed that the distances between any two rings is greater than 600 000.

Remember that a human can very easily solve this task, so make sure that no human traitors are helping the Cybermen complete this task.

Input

The first line contains an integer k (1 ≤ k ≤ 4), the number of rings.

The second line contains an integer n (100 ≤ n ≤ 1 000), the number of samples per ring.

The following n × k lines contain the samples, one sample per line.

Each line contains a pair of integers x_i, y_i, where (x_i, y_i) are the coordinates of the i-th sample.

Output

Print k lines, each describing a single ring.

For each line, print three real numbers x_i, y_i, r_i, where (x_i, y_i) and r_i are the coordinates and the radius of the i-th ring.

The order of the rings does not matter.

Note

Here is how one of tests with k=4 and n=100 looks like. 

<image>

You can download the sample input and output [here](//assets.codeforces.com/rounds/1184/c1.zip).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() { return abs((int)mt()); }
struct point_t {
  double x, y;
  point_t() : x(0), y(0) {}
  point_t(double x, double y) : x(x), y(y) {}
  point_t(const point_t& p) : x(p.x), y(p.y) {}
  int operator<(const point_t& rhs) const {
    return make_pair(y, x) < make_pair(rhs.y, rhs.x);
  }
  int operator==(const point_t& rhs) const {
    return make_pair(y, x) == make_pair(rhs.y, rhs.x);
  }
  point_t operator+(const point_t& p) const {
    return point_t(x + p.x, y + p.y);
  }
  point_t operator-(const point_t& p) const {
    return point_t(x - p.x, y - p.y);
  }
  point_t operator*(double c) const { return point_t(x * c, y * c); }
  point_t operator/(double c) const { return point_t(x / c, y / c); }
};
double cross(point_t p, point_t q) { return p.x * q.y - p.y * q.x; }
double area(point_t a, point_t b, point_t c) {
  return fabs(cross(a, b) + cross(b, c) + cross(c, a)) / 2;
}
double area2(point_t a, point_t b, point_t c) {
  return cross(a, b) + cross(b, c) + cross(c, a);
}
double dot(point_t p, point_t q) { return p.x * q.x + p.y * q.y; }
double dist(point_t p, point_t q) { return sqrt(dot(p - q, p - q)); }
double dist2(point_t p, point_t q) { return dot(p - q, p - q); }
point_t RotateCCW90(point_t p) { return point_t(-p.y, p.x); }
point_t RotateCW90(point_t p) { return point_t(p.y, -p.x); }
point_t RotateCCW(point_t p, double t) {
  return point_t(p.x * cos(t) - p.y * sin(t), p.x * sin(t) + p.y * cos(t));
}
int sign(double x) { return x < -1e-9 ? -1 : x > 1e-9; }
int sign(double x, double y) { return sign(x - y); }
ostream& operator<<(ostream& os, const point_t& p) {
  os << "(" << p.x << "," << p.y << ")";
  return os;
}
point_t ProjectPointLine(point_t a, point_t b, point_t c) {
  return a + (b - a) * dot(c - a, b - a) / dot(b - a, b - a);
}
double DistancePointLine(point_t a, point_t b, point_t c) {
  return dist(c, ProjectPointLine(a, b, c));
}
point_t ComputeLineIntersection(point_t a, point_t b, point_t c, point_t d) {
  b = b - a;
  d = c - d;
  c = c - a;
  return a + b * cross(c, d) / cross(b, d);
}
struct Line {
  point_t l, r;
  Line() {}
  Line(point_t l, point_t r) : l(l), r(r) {}
  Line(const Line& rhs) : l(rhs.l), r(rhs.r) {}
};
Line Bisector(point_t a, point_t b) {
  point_t c = (a + b) / 2;
  return Line(c, c + RotateCCW90(b - c));
}
struct Circle {
  point_t cen;
  double rad;
  Circle() : rad(0) {}
  Circle(point_t cen, double rad) : cen(cen), rad(rad) {}
  Circle(const Circle& rhs) : cen(rhs.cen), rad(rhs.rad) {}
  int operator<(const Circle& rhs) const { return rad < rhs.rad; }
};
Circle CircumCircle(point_t a, point_t b, point_t c) {
  if (sign(cross(a - c, b - c)) == 0) {
    Circle res = Circle((a + b) / 2, dist(a, b) / 2);
    res = max(res, Circle((b + c) / 2, dist(b, c) / 2));
    res = max(res, Circle((c + a) / 2, dist(c, a) / 2));
    return res;
  }
  Line ln1 = Bisector(a, b);
  Line ln2 = Bisector(b, c);
  point_t cen = ComputeLineIntersection(ln1.l, ln1.r, ln2.l, ln2.r);
  return Circle(cen, dist(cen, a));
}
void chemthan() {
  int k, n;
  cin >> k >> n;
  vector<point_t> pts(n * k);
  for (point_t& p : pts) cin >> p.x >> p.y;
  vector<Circle> res;
  auto calc = [&](Circle c) {
    int cnt = 0;
    for (int i = (0); i < (int((pts).size())); ++i) {
      double d = dist(c.cen, pts[i]);
      if (abs(d - c.rad) < 5e4) {
        cnt++;
      }
    }
    if (!cnt) return 1e9;
    return abs(cnt - (double)int((pts).size()) / (k - int((res).size())));
  };
  for (int it = (0); it < (k); ++it) {
    vector<pair<double, Circle>> candidates;
    for (int it = (0); it < (1000); ++it) {
      int u = mrand() % int((pts).size());
      int v = mrand() % int((pts).size());
      int w = mrand() % int((pts).size());
      if (5e4 < dist(pts[u], pts[v]) && 5e4 < dist(pts[v], pts[w]) &&
          5e4 < dist(pts[w], pts[u])) {
        Circle c = CircumCircle(pts[u], pts[v], pts[w]);
        candidates.push_back(make_pair(calc(c), c));
      }
    }
    sort((candidates).begin(), (candidates).end());
    Circle tmp;
    for (auto e : candidates) {
      Circle c = e.second;
      int found = 0;
      for (Circle cc : res) {
        double d = dist(c.cen, cc.cen);
        if (d < 0.1 * 600000) {
          found = 1;
          break;
        }
      }
      if (!found) {
        tmp = c;
        break;
      }
    }
    res.push_back(tmp);
    for (int i = (int((pts).size())) - 1; i >= (0); --i) {
      double d = dist(pts[i], res.back().cen);
      if (abs(d - res.back().rad) < 5e4) {
        pts.erase(pts.begin() + i);
      }
    }
    cerr << "["
         << "sz(pts)"
         << ": " << (int((pts).size())) << "] ";
    cerr << "\n";
    ;
  }
  assert(int((res).size()) == k);
  for (Circle c : res) {
    cout << fixed << setprecision(9) << c.cen.x << " " << c.cen.y << " "
         << c.rad << "\n";
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

```