Problem: The Galaxy contains n planets, there are many different living creatures inhabiting each planet. And each creature can get into troubles! Space rescuers know it perfectly well and they are always ready to help anyone who really needs help. All you need to do is call for them. 

Now the space rescuers plan to build the largest in the history of the Galaxy rescue station; however, the rescue station's location is yet to be determined. As some cases are real emergencies, the rescuers want to find such a point in the Galaxy from which it would be possible to get to the remotest planet in the minimum possible time. In other words, the rescuers need such point in the space that the distance between it and the planet remotest from it was minimal (if we compare this point with all other possible points in the space). Unfortunately, the rescuers can't sole this problem.

As the planets are quite remote from each other, they can be considered as points in Euclidean three-dimensional space. The distance between points (xi, yi, zi) and (xj, yj, zj) can be calculated by the formula <image>. The rescue station can be positioned in any point in the space. It can also coincide with some planet. 

Galaxy is in danger! Save the space rescuers and find the required point for them.

Input

The first line of the input file contains integer n — the number of planets (1 ≤ N ≤ 100). Each of the following n lines contains information about the planets. The i-th line contains three integers xi, yi, zi — the coordinates of the i-th planet ( - 104 ≤ xi, yi, zi ≤ 104, 1 ≤ i ≤ n). No two planets coincide.

Output

Print on the first line of the output file three space-separated real numbers x0, y0, z0 — the coordinates for the future base. If there are several solutions, you are allowed to print any of them. The answer will be accepted if the distance from this point to the remotest planet will differ from the juries' variant in no more than 10 - 6 in absolute or relative value.

Examples

Input

5
5 0 0
-5 0 0
0 3 4
4 -3 0
2 2 -2


Output

0.000 0.000 0.000

Solution (in JAVA):

Solution:


import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;

public class ProblemE_82 {
    
    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE")!=null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");
    
    void init() throws FileNotFoundException{
        if (ONLINE_JUDGE){
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }else{
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }
    
    String readString() throws IOException{
        while(!tok.hasMoreTokens()){
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }
    
    int readInt() throws IOException{
        return Integer.parseInt(readString());
    }
    
    long readLong() throws IOException{
        return Long.parseLong(readString());
    }
    
    double readDouble() throws IOException{
        return Double.parseDouble(readString());
    }
    
    public static void main(String[] args){
        new ProblemE_82().run();
    }
    
    public void run(){
        try{
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = "+(t2-t1));
        }catch (Exception e){
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }
    
    static class Utils {

        private Utils() {}

        public static void mergeSort(int[] a) {
            mergeSort(a, 0, a.length - 1);
        }

        private static void mergeSort(int[] a, int leftIndex, int rightIndex) {
            final int MAGIC_VALUE = 50;
            if (leftIndex < rightIndex) {
                if (rightIndex - leftIndex <= MAGIC_VALUE) {
                    insertionSort(a, leftIndex, rightIndex);
                } else {
                    int middleIndex = (leftIndex + rightIndex) / 2;
                    mergeSort(a, leftIndex, middleIndex);
                    mergeSort(a, middleIndex + 1, rightIndex);
                    merge(a, leftIndex, middleIndex, rightIndex);
                }
            }
        }

        private static void merge(int[] a, int leftIndex, int middleIndex, int rightIndex) {
            int length1 = middleIndex - leftIndex + 1;
            int length2 = rightIndex - middleIndex;
            int[] leftArray = new int[length1];
            int[] rightArray = new int[length2];
            System.arraycopy(a, leftIndex, leftArray, 0, length1);
            System.arraycopy(a, middleIndex + 1, rightArray, 0, length2);
            for (int k = leftIndex, i = 0, j = 0; k <= rightIndex; k++) {
                if (i == length1) {
                    a[k] = rightArray[j++];
                } else if (j == length2) {
                    a[k] = leftArray[i++];
                } else {
                    a[k] = leftArray[i] <= rightArray[j] ? leftArray[i++] : rightArray[j++];
                }
            }
        }

        private static void insertionSort(int[] a, int leftIndex, int rightIndex) {
            for (int i = leftIndex + 1; i <= rightIndex; i++) {
                int current = a[i];
                int j = i - 1;
                while (j >= leftIndex && a[j] > current) {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = current;
            }
        }

    }
    
    class Point3D{
        
        double x, y, z;
        
        public Point3D(double x, double y, double z){
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
    
    int n;
    Point3D[] p;
    int iter = 45; // Magic number =)
    Point3D ans;
    
    public double dist(double x, double y, double z, Point3D p){
        return (x - p.x) * (x - p.x)+ (y - p.y) * (y - p.y) + (z - p.z) * (z - p.z);
    }
    
    double fz(double x, double y, double z){
        double max = 0;
        for (int i = 0; i < n; i++){
            max = max(max, dist(x, y, z, p[i]));
        }
        return max;
    }
    
    double fy(double x, double y){
        double lz = -1e5;
        double rz = 1e5;
        for (int it = 0; it < iter; it++){
            double z1 = (lz + rz) / 2 - (rz - lz) / 100;
            double z2 = (lz + rz) / 2 + (rz - lz) / 100;
            if (fz(x, y, z1) < fz(x, y, z2)) rz = z2;
            else lz = z1;
        }
        ans.z = (lz + rz) / 2;
        return fz(x, y, ans.z);
    }
    
    double fx(double x){
        double ly = -1e5;
        double ry = 1e5;
        for (int it = 0; it < iter; it++){
            double y1 = (ly + ry) / 2 - (ry - ly) / 100;
            double y2 = (ly + ry) / 2 + (ry - ly) / 100;
            if (fy(x, y1) < fy(x, y2)) ry = y2;
            else ly = y1;
        }
        ans.y = (ly + ry) / 2;
        return fy(x, ans.y);
    }
    
    void solve() throws IOException{
        n = readInt();
        p = new Point3D[n];
        for (int i = 0; i < n; i++){
            p[i] = new Point3D(readDouble(), readDouble(), readDouble());
        }
        ans = new Point3D(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);
        double lx = -1e5;
        double rx = 1e5;
//      for (int itx = 0; itx < iter; itx++){
//          double mx1 = (lx + rx) / 2 - (rx - lx) / 100;
//          ly = -10000;
//          ry = 10000;
//          for (int ity = 0; ity < iter; ity++){
//              double my1 = (ly + ry) / 2 - (ry - ly) / 100;
//              lz = -10000;
//              rz = 10000;
//              for (int itz = 0; itz < iter; itz++){
//                  double mz1 = (lz + rz) / 2 - (rz - lz) / 100;
//                  double mz2 = (lz + rz) / 2 + (rz - lz) / 100;
//                  double fz1 = 0;
//                  double fz2 = 0;
//                  for (int i = 0; i < n; i++){
//                      fz1 = max(fz1, dist(mx1, my1, mz1, p[i]));
//                      fz2 = max(fz2, dist(mx1, my1, mz2, p[i]));
//                  }
//                  if (fz1 < fz2) rz = mz2;
//                  else lz = mz1;
//              }
//              ans.z = (lz + rz) / 2;
//              double fy1 = 0;
//              for (int i = 0; i < n; i++){
//                  fy1 = max(fy1, dist(mx1, my1, ans.z, p[i]));
//              }
//              double my2 = (ly + ry) / 2 + (ry - ly) / 100;
//              lz = -10000;
//              rz = 10000;
//              for (int itz = 0; itz < iter; itz++){
//                  double mz1 = (lz + rz) / 2 - (rz - lz) / 100;
//                  double mz2 = (lz + rz) / 2 + (rz - lz) / 100;
//                  double fz1 = 0;
//                  double fz2 = 0;
//                  for (int i = 0; i < n; i++){
//                      fz1 = max(fz1, dist(mx1, my2, mz1, p[i]));
//                      fz2 = max(fz2, dist(mx1, my2, mz2, p[i]));
//                  }
//                  if (fz1 < fz2) rz = mz2;
//                  else lz = mz1;
//              }
//              ans.z = (lz + rz) / 2;
//              double fy2 = 0;
//              for (int i = 0; i < n; i++){
//                  fy2 = max(fy2, dist(mx1, my2, ans.z, p[i]));
//              }
//              if (fy1 < fy2) ry = my2;
//              else ly = my1;
//          }
//          ans.y = (ly + ry) / 2;
//          double fx1 = 0;
//          for (int i = 0; i < n; i++){
//              fx1 = max(fx1, dist(mx1, ans.y, ans.z, p[i]));
//          }
//          double mx2 = (lx + rx) / 2 + (rx - lx) / 100;
//          ly = -10000;
//          ry = 10000;
//          for (int ity = 0; ity < iter; ity++){
//              double my1 = (ly + ry) / 2 - (ry - ly) / 100;
//              lz = -10000;
//              rz = 10000;
//              for (int itz = 0; itz < iter; itz++){
//                  double mz1 = (lz + rz) / 2 - (rz - lz) / 100;
//                  double mz2 = (lz + rz) / 2 + (rz - lz) / 100;
//                  double fz1 = 0;
//                  double fz2 = 0;
//                  for (int i = 0; i < n; i++){
//                      fz1 = max(fz1, dist(mx2, my1, mz1, p[i]));
//                      fz2 = max(fz2, dist(mx2, my1, mz2, p[i]));
//                  }
//                  if (fz1 < fz2) rz = mz2;
//                  else lz = mz1;
//              }
//              ans.z = (lz + rz) / 2;
//              double fy1 = 0;
//              for (int i = 0; i < n; i++){
//                  fy1 = max(fy1, dist(mx2, my1, ans.z, p[i]));
//              }
//              double my2 = (ly + ry) / 2 + (ry - ly) / 100;
//              lz = -10000;
//              rz = 10000;
//              for (int itz = 0; itz < iter; itz++){
//                  double mz1 = (lz + rz) / 2 - (rz - lz) / 100;
//                  double mz2 = (lz + rz) / 2 + (rz - lz) / 100;
//                  double fz1 = 0;
//                  double fz2 = 0;
//                  for (int i = 0; i < n; i++){
//                      fz1 = max(fz1, dist(mx2, my2, mz1, p[i]));
//                      fz2 = max(fz2, dist(mx2, my2, mz2, p[i]));
//                  }
//                  if (fz1 < fz2) rz = mz2;
//                  else lz = mz1;
//              }
//              ans.z = (lz + rz) / 2;
//              double fy2 = 0;
//              for (int i = 0; i < n; i++){
//                  fy2 = max(fy2, dist(mx2, my2, ans.z, p[i]));
//              }
//              if (fy1 < fy2) ry = my2;
//              else ly = my1;
//          }
//          ans.y = (ly + ry) / 2;
//          double fx2 = 0;
//          for (int i = 0; i < n; i++){
//              fx2 = max(fx2, dist(mx2, ans.y, ans.z, p[i]));
//          }
//          if (fx1 < fx2) rx = mx2;
//          else lx = mx1;
//      }
        for (int it = 0; it < iter; it++){
            double x1 = (lx + rx) / 2 - (rx - lx) / 100;
            double x2 = (lx + rx) / 2 + (rx - lx) / 100;
            if (fx(x1) < fx(x2)) rx = x2;
            else lx = x1;
        }
        ans.x = (lx + rx) / 2;
        out.printf(Locale.US, "%.8f", ans.x);
        out.print(" ");
        out.printf(Locale.US, "%.8f", ans.y);
        out.print(" ");
        out.printf(Locale.US, "%.8f", ans.z);
    }
}