Problem: Problem A: Approximate Circle

Consider a set of n points (x1, y1), ..., (xn,yn) on a Cartesian space. Your task is to write a program for regression to a circle x2 + y2 + ax + by + c = 0. In other words, your program should find a circle that minimizes the error. Here the error is measured by the sum over square distances between each point and the circle, which is given by:

<image>



Input

The input begins with a line containing one integer n (3 <= n <= 40,000). Then n lines follow. The i-th line contains two integers xi and yi (0 <= xi, yi <= 1,000), which denote the coordinates of the i-th point.

You can assume there are no cases in which all the points lie on a straight line.

Output

Print three integers a, b and c, separated by space, to show the regressed function. The output values should be in a decimal fraction and should not contain an error greater than 0.001.

Examples

Input

4
0 0
100 0
100 100
0 100


Output

-100.000 -100.000 0.000


Input

3
0 0
10 0
5 100


Output

-10.000 -99.750 0.000

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define sgn(v) (abs((v))<eps?0:((v)<0?-1:1))
#define sqr(v) ((v)*(v))
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
#define debug 0
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<double,int> PDI;
typedef pair<double,double> PDD;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<LL,LL> PLL;
typedef long double Double;
const Double eps=1e-8;
const Double pi=acos(-1);
using namespace std;
const int maxn=4e4+100;
Double x[maxn],y[maxn];
Double a[3][3],c[3][3],b[3];
Double replace(int ix)
{
    int i,j;
    double res=0;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)c[i][j]=a[i][j];
    for(j=0;j<3;++j)c[ix][j]=b[j];
    for(i=0;i<3;++i)
    {
        res+=c[0][i]*c[1][(i+1)%3]*c[2][(i+2)%3];
        res-=c[0][i]*c[1][(i+2)%3]*c[2][(i+1)%3];
    }
    return res;
}
int main()
{
    int n,i;
	//cout <<sizeof(double)<<" "<<sizeof(long double)<<" "<<sizeof(float)<<" "<<sizeof(int)<<endl;
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(i=0;i<n;++i)
    {
        scanf("%Lf%Lf",&x[i],&y[i]);
        b[0]+=(sqr(x[i])+sqr(y[i]))*x[i];
        b[1]+=(sqr(x[i])+sqr(y[i]))*y[i];
        b[2]+=(sqr(x[i])+sqr(y[i]));
        a[0][0]+=sqr(x[i]);a[0][1]+=x[i]*y[i];a[0][2]+=x[i];
        a[1][0]+=x[i]*y[i];a[1][1]+=sqr(y[i]);a[1][2]+=y[i];
        a[2][0]+=x[i];a[2][1]+=y[i];a[2][2]+=1;
    }
    for(i=0;i<3;++i)b[i]=-b[i];
    Double delta=0;
    for(i=0;i<3;++i)
    {
        delta+=a[0][i]*a[1][(i+1)%3]*a[2][(i+2)%3];
        delta-=a[0][i]*a[1][(i+2)%3]*a[2][(i+1)%3];
    }
    //cout <<delta<<endl;
    Double A=replace(0)/delta;
    Double B=replace(1)/delta;
    Double C=replace(2)/delta;
    printf("%.3Lf %.3Lf %.3Lf\n",A,B,C);
    //printf("%.9f %.9f %.9f\n",A,B,C);
    return 0;
}