/////////////////////////////////////////////////////////////////////////////////////////////
//
//   MatrixMultiplyRA.java
//   Multiplies any number of matrices using rational arithmetic.
//
//   1. Save this file as MatrixMultiplyRA.java on any system with the javac compiler, available
//      from Sun Microsystems: http://java.sun.com/javase/downloads/index.jsp
//   2. If you're on a unix system also save the file "Makefile" in the same directory, then
//   3.      Compile by typing "make" or "gmake" at the command line (leave out the quotes).
//   4.      Run the executable by doing "MatrixMultiplyRA infile outfile", where "infile" is
//           a properly formated (described below) input file.
//   5. Else if you're on any other system, then
//   6.      Compile by typing "javac MatrixMultiplyRA.java" at the command line (leave out quotes).
//   7.      Run the executable by doing "java MatrixMultiplyRA infile outfile, where "infile" is
//           a properly formated (described below) input file.
//
//   Input file format.
//   The first line of an input file consists of two integers n and p, separated by a space,
//   giving the number of rows and columns of the first matrix.  The next n lines of the input
//   file specify the n rows of the first matrix.  Each line is a space separated list of p rational
//   numbers.  A rational number is represented by either a single string of digits, or a pair
//   of such strings separated by a fraction bar "/".  Note that the number of spaces separating the
//   numbers in each row is irrelevant.

//   The next line of the input file consists of two integers p and m, separated by a space, giving
//   the number of rows and columns of the second matrix.  Necessarily the number of columns of
//   the first matrix, and the number of rows of the second matrix must be one and the same,
//   namely p.  The next p lines of input specify the p rows of the second matrix, each of which
//   is a space separated list of m rational numbers.  Each subsequent matrix is specified in the same
//   way, with the number of columns of one matrix equaling the number of rows of the next.  The
//   input is terminated by either a blank line, or by the eof character.
//
//   Output file format:
//   The output file will be formated in the same way as the input file, i.e. two integers on
//   a line, giving the number of rows and columns, followed by each row of the product matrix,
//   and terminated by eof.  Note that unlike the GaussJordan programs, this program does not
//   overwrite a pre existing output file.  If the output file does not already exist, it is
//   created.  If it does exist, output is appended to the existing lines.  Thus one can build up
//   several products into one output file, and if the resulting matrices have the proper
//   dimensions, that output file can be used as input to another run of the program.
//
//   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
//   5 4
//    1  3  8  1
//    2  6  7  0
//    1 -3  5  0
//    0  5 -2  6
//   -1  2  0 10
//
//   Example 2  (Save as text file in2.)
//   4 4
//    3/2  4/5  7    0
//   -6    1/2  3/4  5/6
//    2    7    4    3
//    6/7  8/8 -9    2/5
//   4 3
//    0    1    8
//    7/8  0    0
//    2    2/3  4/5
//    3    4/7 -5
//   3 2
//    2/3  3/4
//    5    9
//    2   -1/3
//
//   The result of Example 1 is a 3x4 matrix, while Example 2 yields a 4x2.  Run the
//   program on the two files in succession, with the output file name in3.  Then in3
//   is a properly formated input file, on which you can run the program again. Do
//
//   % MatrixMultiplyRA  in1  in3
//   % MatrixMultiplyRA  in2  in3
//   % MatrixMultiplyRA  in3  out
//
//   File out will then contain the product of all five matrices, which is a 3x2.
//
/////////////////////////////////////////////////////////////////////////////////////////////

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

class MatrixMultiplyRA{

   // mult()
   // Return a new matrix which is the product of matrices A and B.
   // pre: #columns(A)=#rows(B)
   static Rational[][] mult(Rational[][] A, Rational[][] B){
      int i, k, j, n, p, q, m;
      n = A.length - 1;
      p = A[0].length - 1;
      q = B.length - 1;
      m = B[0].length - 1;
      if( p!=q ){
         throw new RuntimeException("MatrixMultiplyRA: mult: matrix dimensions do not match");
      }
      Rational[][] P = new Rational[n+1][m+1];
      for(i=1; i<=n; i++){
         for(j=1; j<=m; j++){
            P[i][j] = Rational.valueOf(0);
            for(k=1; k<=p; k++) P[i][j].addEq(A[i][k].mult(B[k][j]));
         }
      }
      return P;
   }

   // printMatrix()
   // print Matrix A to file out
   static void printMatrix(FileOutputStream out, Rational[][] A) throws IOException{
      int n = A.length - 1;
      int m = A[0].length - 1;
      StringBuffer sb = new StringBuffer(n + " " + m + "\n");
      for(int i=1; i<=n; i++){
         for(int j=1; j<=m; j++) sb.append(A[i][j] + " ");
         sb.append("\n");
      }
      out.write(sb.toString().getBytes());
   }

   // main()
   // read input file, build up the product one factor at a time, then append
   // the resulting matrix to the output file.
   public static void main(String[] args) throws IOException {
      int n, p, m, i, k, j;
      String line;
      StringTokenizer st;
      Rational[][] Product;
      Rational[][] A;

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

      // read in first matrix, get it's dimensions
      st = new StringTokenizer(in.readLine());
      n = Integer.parseInt(st.nextToken());
      p = Integer.parseInt(st.nextToken());

      // allocate Product to be of size (n+1)x(p+1), don't use index 0
      Product = new Rational[n+1][p+1];

      // read in each row
      for(i=1; i<=n; i++){
         st = new StringTokenizer(in.readLine());
         for(k=1; k<=p; k++){
            Product[i][k] = Rational.valueOf(st.nextToken());
         }
      }

      // read in remaining matrices, and build up Product
      st = new StringTokenizer((line=in.readLine())==null?" ":line);
      while(st.countTokens()>=2){ // there is another matrix to read

         // get it's dimensions
         p = Integer.parseInt(st.nextToken());
         m = Integer.parseInt(st.nextToken());

         // check that dimensions are compatible
         if( p != (Product[0].length - 1) ){
            throw new RuntimeException("MatrixMultiplyRA: matrix dimensions do not match");
         }

         // allocate A to be of size (p+1)x(m+1), don't use index 0
         A = new Rational[p+1][m+1];

         // read in each row
         for(k=1; k<=p; k++){
            st = new StringTokenizer(in.readLine());
            for(j=1; j<=m; j++){
               A[k][j] = Rational.valueOf(st.nextToken());
            }
         }

         // build up Product by multiplying by A
         Product = mult(Product, A);

         // get dimensiions of the next matrix
         st = new StringTokenizer( (line=in.readLine())==null?" ":line );
      }

      // close input file
      in.close();

      // print Product to output file
      printMatrix(out, Product);

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