import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.util.*;
import java.applet.*;
import java.net.URL;

public class NumAnal {

    public static double[][] makeAlexMatx(int[][] codedMatx, int t) {
        int n = codedMatx.length;
        double[][] a = new double[n][n];
        for (int ii = 0; ii < n; ii++)
            for (int j = 0; j < n; j++) a[ii][j] = 0;
        for (int ii = 0; ii < n; ii++) {
            a[ii][codedMatx[ii][0]] = 1-t;
            a[ii][codedMatx[ii][1]] = -1;
            a[ii][codedMatx[ii][2]] = t;
        }
        return a;
    }

    public static double det(double[][] A, int n) {
        // calculate determinant of the top n-by-n part of A
        // use Gaussian elimination
        // destroys A in the process
        for (int ii = 0; ii < n; ii++)
            for (int j = 0; j < n; j++)
                System.out.print(A[ii][j] + " ");
        boolean negFlag = false;
        for (int ii = 0; ii < n; ii++) {
            // pivot if necessary
            int iii = ii;
            while (iii < n) {
                if (A[iii][ii] != 0) break;
                iii++;
            }
            if ( !(iii < n ) ) return 0.0;
            if (iii != ii) {
                negFlag = !negFlag;
                double[] tempRow = A[ii];
                A[ii] = A[iii];
                A[iii] = tempRow;
            }
            for (int j = ii+1; j < n; j++) {
                // reduce remaining rows
                if (A[j][ii] == 0) continue;
                double factor = A[j][ii]/A[ii][ii];
                A[j][ii] = 0;
                for (int k = ii+1; k < n; k++)
                    A[j][k] -= factor*A[ii][k];
            }
        }
        double res = A[0][0];
        for (int ii = 0; ii < n; ii++) res *= A[ii][ii];
        if (negFlag) res = -res;
        System.out.println(": " + res);
        return res;
    }

    public static double[] newtonInterp(int[][] codedMatx) {
        int n = codedMatx.length; // degree = n-1
        for (int ii = 0; ii < n; ii++)
            System.out.println(codedMatx[ii][0] + " " +
                    codedMatx[ii][1] + " " +
                    codedMatx[ii][2]);
        // calculate function values at –(n/2), -(n/2)+1, …
        int startValue = -(n/2);
        double[] f = new double[n];
        for (int ii = 0; ii < n; ii++)
            f[ii] = Math.round(det(makeAlexMatx(codedMatx, startValue+ii), n-1));
        for (int ii = 0; ii < n; ii++)
            System.out.print( ((int) f[ii]) + " ");
        System.out.println();
        // now calculate divided differences
        for (int ii = 1; ii < n; ii++)
            for (int j = n-1; j >= 1; j--)
                f[j] = (f[j]-f[j-1])/ii;
        for (int ii = 0; ii < n; ii++)
            System.out.print( f[ii] + " " );
        System.out.println();
        // now calculate the polynomial
        double[] a = new double[n];
        a[0] = f[n-1];
        int d = 0; // current degree
        for (int iii = n-2; iii >= 0; iii--) {
            int ii = iii + startValue;
            // poly  poly*(x-ii)+f[iii]
            a[d+1] = a[d];
            for (int j = d; j > 0; j--)
                a[j] = a[j-1] - ii*a[j];
            a[0] = f[iii] - ii*a[0];
            d++;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
    }

}