Spectator Riots

It’s riot time on football stadium Ramacana! Raging fans have entered the field and the police find themselves in a difficult situation. The field can be represented as a square in the coordinate system defined by two diagonal vertices in (0,0) and (10⁵, 10⁵). The sides of that square are also considered to be inside the field, everything else is outside.

In the beginning, there are N fans on the field. For each fan we are given his speed, an integer v _i as well as his integer coordinates ( x _i, y _i). A fan with those coordinates might move and after one second he might be at any point ( x _i + p, y _i + q) where 0 ≤ |p| + |q| ≤ v _i. p, q are both integers.

Points that go outside of the square that represents the field are excluded and all others have equal probability of being the location of that specific fan after one second.

Andrej, a young and promising police officer, has sent a flying drone to take a photo of the riot from above. The drone’s camera works like this:

1. It selects three points with integer coordinates such that there is a chance of a fan appearing there after one second. They must not be collinear or the camera won’t work. It is guaranteed that not all of the initial positions of fans will be on the same line.
2. Camera focuses those points and creates a circle that passes through those three points. A photo is taken after one second (one second after the initial state).
3. Everything that is on the circle or inside it at the moment of taking the photo (one second after focusing the points) will be on the photo.

Your goal is to select those three points so that the expected number of fans seen on the photo is maximized. If there are more such selections, select those three points that give the circle with largest radius among them. If there are still more suitable selections, any one of them will be accepted. If your answer follows conditions above and radius of circle you return is smaller then the optimal one by 0.01, your output will be considered as correct.

No test will have optimal radius bigger than 10¹⁰.

Input

The first line contains the number of fans on the field, N. The next N lines contain three integers: x _i , y _i, v _i. They are the x-coordinate, y-coordinate and speed of fan i at the beginning of the one second interval considered in the task.

• 3 ≤ N ≤ 10⁵
• 0 ≤ x _i, y _i ≤ 10⁵
• 0 ≤ v _i ≤ 1000
• All numbers are integers

Output

You need to output the three points that camera needs to select. Print them in three lines, with every line containing the x-coordinate, then y-coordinate, separated by a single space. The order of points does not matter.

Examples

input

3
1 1 1
1 1 1
1 2 1

output

2 2
2 1
1 0

Solution:

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100000;
const int N = 400010;

int x[N], y[N];
long long dist[N];
int km;

inline bool cmp(int i, int j) {
int xi = x[i] - x[km];
int yi = y[i] - y[km];
int xj = x[j] - x[km];
int yj = y[j] - y[km];
long long vmul = xi * 1LL * yj - xj * 1LL * yi;
if (vmul != 0) {
return (vmul > 0);
}
return dist[i] < dist[j];
}

int mn[MAX + 10], mx[MAX + 10];
int id[N];
int nx[N], ny[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i <= MAX; i++) {
    mn[i] = MAX + 1;
    mx[i] = -1;
  }
  for (int i = 0; i < n; i++) {
    int px, py, pv;
    scanf("%d %d %d", &px, &py, &pv);
    for (int s = -pv; s <= pv; s++) {
      int from = py - pv + abs(s);
      int to = py + pv - abs(s);
      from = max(from, 0);
      to = min(to, MAX);
      int xx = px + s;
      if (0 <= xx && xx <= MAX) {
        mn[xx] = min(mn[xx], from);
        mx[xx] = max(mx[xx], to);
      }
    }
  }
  n = 0;
  for (int i = 0; i <= MAX; i++) {
    if (mx[i] != -1) {
      x[n] = i;
      y[n] = mn[i];
      n++;
      if (mn[i] < mx[i]) {
        x[n] = i;
        y[n] = mx[i];
        n++;
      }
    }
  }
  km = 0;
  for (int i = 1; i < n; i++) {
    if (y[i] < y[km] || (y[i] == y[km] && x[i] < x[km])) {
      km = i;
    }
  }
  for (int i = 0; i < n; i++) {
    dist[i] = (x[i] - x[km]) * 1LL * (x[i] - x[km]) + (y[i] - y[km]) * 1LL * (y[i] - y[km]);
    id[i] = i;
  }
  sort(id, id + n, cmp);
  for (int i = 0; i < n; i++) {
    nx[i] = x[id[i]];
    ny[i] = y[id[i]];
  }
  for (int i = 0; i < n; i++) {
    x[i] = nx[i];
    y[i] = ny[i];
  }
  int e = 1;
  for (int i = 1; i < n; i++) {
    while (e > 1) {
long long a = y[e - 1] - y[e - 2];
long long b = x[e - 2] - x[e - 1];
long long c = -a * x[e - 1] - b * y[e - 1];
long long z = a * x[i] + b * y[i] + c;
if (z >= 0) {
e--;
} else {
break;
}
}
x[e] = x[i];
y[e] = y[i];
e++;
}
n = e;
double ans = -1.0;
int pos = -1;
for (int i = 0; i < n; i++) {
    long long xa = x[i];
    long long ya = y[i];
    long long xb = x[(i + 1) % n];
    long long yb = y[(i + 1) % n];
    long long xc = x[(i + 2) % n];
    long long yc = y[(i + 2) % n];
    double a = sqrt((xc - xb) * (xc - xb) + (yc - yb) * (yc - yb));
    double b = sqrt((xa - xc) * (xa - xc) + (ya - yc) * (ya - yc));
    double c = sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
    double area = 0.5 * abs((xa - xb) * (ya + yb) + (xb - xc) * (yb + yc) + (xc - xa) * (yc + ya));
    double rad = a * b * c / (4 * area);
    if (rad > ans) {
ans = rad;
pos = i;
}
}
int i = pos;
long long xa = x[i];
long long ya = y[i];
long long xb = x[(i + 1) % n];
long long yb = y[(i + 1) % n];
long long xc = x[(i + 2) % n];
long long yc = y[(i + 2) % n];
cout << xa << " " << ya << endl;
  cout << xb << " " << yb << endl;
  cout << xc << " " << yc << endl;
  return 0;
}