/////////////////////////////////////////////////////////////////////////////////////////////
//
//   GaussJordanRA.java
//   Runs Gauss Jordan Elimination on a matrix using rational arithmetic
//   Uses the Rational class defined file Rational.java
//
//   1. Save this file as GaussJordanRA.java on any system with the javac compiler, available
//      from Sun Microsystems: http://java.sun.com/javase/downloads/index.jsp
//   2. Also save Rational.java in the same directory.
//   3. If you're on a unix system also save the file "Makefile" in the same directory, then
//   4.      Compile by typing "make" or "gmake" at the command line (leave out the quotes).
//   5.      Run the executable by doing "GaussJordanRA infile outfile", where "infile" is
//           a properly formated (described below) input file.
//   6. Else if you're on any other system, then
//   7.      Compile by typing "javac GaussJordanRA.java" at the command line (leave out quotes).
//   8.      Run the executable by doing "java GaussJordanRA infile outfile, where "infile" is
//           a properly formated (described below) input file.
//
//   Note: if "outfile" already exists in your working directory, then the above commands will
//         overwrite it.
//
//   Input file format.
//   The first line of an input file consists of two integers n and m, separated by a space,
//   giving the number of rows and columns, respectively.  The next n lines of the input file
//   specify the n rows of the matrix.  Each line is a space separated list of m rational
//   numbers, expressed either as a signed integer or a pair of signed integers separated by
//   a fraction bar.  Note that the number of spaces separating the numbers in each row is
//   irrelevant.
//
//   Example 1  (Save the following lines as a text file called in1.)
//   3 5
//   2 0 4 2   9
//   3 4 0 0  -7
//   0 1 0 5   0
//
//   Example 2  (Save as text file in2.)
//   4 7
//    3    4/5  7/9    0   0     1      8/2
//   -7    1/2  3      5   7/8   0      0
//    9/8  7/6  5      3   2     2/3    4/5
//   -6/7  8/8  9/-11  2   3     4/7   -5/5
//
/////////////////////////////////////////////////////////////////////////////////////////////

import java.io.*;
import java.util.StringTokenizer;

class GaussJordanRA{

   // swap()
   // swap row i with row k
   // pre: A[i][q]==A[k][q]==0 for 1<=q<j
   static void swap(Rational[][] A, int i, int k, int j){
      int m = A[0].length - 1;
      Rational temp;
      for(int q=j; q<=m; q++){
         temp = A[i][q];
         A[i][q] = A[k][q];
         A[k][q] = temp;
      }
   }

   // divide()
   // divide row i by A[i][j]
   // pre: A[i][j]!=0, A[i][q]==0 for 1<=q<j
   // post: A[i][j]==1;
   static void divide(Rational[][] A, int i, int j){
      int m = A[0].length - 1;
      for(int q=m; q>=j; q--) A[i][q].divEq(A[i][j]);
   }

   // eliminate()
   // subtract an appropriate multiple of row i from every other row
   // pre: A[i][j]==1, A[i][q]==0 for 1<=q<j
   // post: A[p][j]==0 for p!=i
   static void eliminate(Rational[][] A, int i, int j){
      int n = A.length - 1;
      int m = A[0].length - 1;
      for(int p=1; p<=n; p++){
         if( p!=i && !A[p][j].isZero() ){
            for(int q=m; q>=j; q--) A[p][q].subEq(A[p][j].mult(A[i][q]));
         }
      }
   }

   // printMatrix()
   // print the present state of Matrix A to file out
   static void printMatrix(PrintWriter out, Rational[][] A){
     int n = A.length - 1;
     int m = A[0].length - 1;
      for(int i=1; i<=n; i++){
         for(int j=1; j<=m; j++) out.print(A[i][j] + "  ");
         out.println();
      }
      out.println();
      out.println();
   }

   // main()
   // read input file, initialize matrix, perform Gauss-Jordan Elimination,
   // and write resulting matrices to output file
   public static void main(String[] args) throws IOException {
      int n, m, i, j, k;
      String line;
      StringTokenizer st;

      // check command line arguments, open input and output files
      if( args.length!=2 ){
         System.out.println("Usage: GaussJordan infile outfile");
         System.exit(1);
      }
      BufferedReader in = new BufferedReader(new FileReader(args[0]));
      PrintWriter out = new PrintWriter(new FileWriter(args[1]));

      // read first line of input file
      line = in.readLine();
      st = new StringTokenizer(line);
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());

      // declare A to be of size (n+1)x(m+1) and do not use index 0
      Rational[][] A = new Rational[n+1][m+1];

      // read next n lines of input file and initialize array A
      for(i=1; i<=n; i++){
         line = in.readLine();
         st = new StringTokenizer(line);
         for(j=1; j<=m; j++){
            A[i][j] = new Rational(st.nextToken());
         }
      }

      // close input file
      in.close();

      // print array A to output file
      printMatrix(out, A);

      // perform Gauss-Jordan Elimination algorithm
      i = 1;
      j = 1;
      while( i<=n && j<=m ){

         //look for a non-zero entry in col j at or below row i
         k = i;
         while( k<=n && A[k][j].isZero() ) k++;

         // if such an entry is found at row k
         if( k<=n ){

            //  if k is not i, then swap row i with row k
            if( k!=i ) {
               swap(A, i, k, j);
               printMatrix(out, A);
            }

            // if A[i][j] is not 1, then divide row i by A[i][j]
            if( A[i][j].compareTo(1)!=0 ){
               divide(A, i, j);
               printMatrix(out, A);
            }

            // eliminate all other non-zero entries from col j by subtracting from each
            // row (other than i) an appropriate multiple of row i
            eliminate(A, i, j);
            printMatrix(out, A);
            i++;
         }
         j++;
      }

      // print rank to output file
      out.println("rank = " + (i-1));

      // close output file
      out.close();
   }
}