import copy
from fractions import *

def copyRationalMatrix(a):
    b = []
    m = len(a)      # Number of rows
    if m == 0:
        raise ValueError("Empty matrix")
    n = len(a[0])   # Number of columns
    if n == 0:
        raise ValueError("Empty matrix row")
    for i in range(m):
        if len(a[i]) != n:
            raise ValueError("Incorrect matrix row")
        row = []
        for j in range(n):
            row.append(Fraction(a[i][j]))
        b.append(row)
    return b

def copyRealMatrix(a):
    b = []
    m = len(a)      # Number of rows
    if m == 0:
        raise ValueError("Empty matrix")
    n = len(a[0])   # Number of columns
    if n == 0:
        raise ValueError("Empty matrix row")
    for i in range(m):
        if len(a[i]) != n:
            raise ValueError("Incorrect matrix row")
        row = []
        for j in range(n):
            row.append(float(a[i][j]))
        b.append(row)
    return b

def swapMatrixRows(a, i, k):
    if i == k:
        return
    assert(0 <= i and i < len(a))
    assert(0 <= k and k < len(a))
    assert(len(a[i]) == len(a[k]))
    n = len(a[i])
    for j in range(n):
        (a[i][j], a[k][j]) = (-a[k][j], a[i][j])
        
def addMatrixLines(a, k, i, c):
    assert(0 <= i and i < len(a))
    assert(0 <= k and k < len(a))
    assert(len(a[i]) == len(a[k]))
    n = len(a[i])
    for j in range(n):
        a[k][j] += c*a[i][j]

def echelonFormOfRationalMatrix(a):
    '''For a matrix a, compute its row echelon matrix and the rank.
       Returns pair: (Echelon form of matrix, rank of matrix)'''
    b = copyRationalMatrix(a)
    m = len(a)      # Number of rows
    n = len(a[0])   # Number of columns
    
    i = 0; j = 0
    while i < m and j < n:
        # Find nonzero element in j-th column, starting
        #      from line i
        imax = (-1)
        for k in range(i, m):
            if b[k][j] != 0:
                imax = k
                break
        if imax < 0:
            # Skip a zero column
            j += 1
            continue
        assert(b[imax][j] != 0)
        
        # Swap rows i and imax and change a sign of one row
        if imax != i:
            swapMatrixRows(b, i, imax)
        r = b[i][j] 
        for k in range(i+1, m):
            c = (-b[k][j])/r
            addMatrixLines(b, k, i, c)
        i += 1; j += 1
    return (b, i)
    
def showRationalMatrix(a):
    # First define a maximal size of matrix elements
    m = len(a)      # Number of rows
    n = len(a[0])   # Number of columns
    assert(m > 0 and n > 0)
    maxSize = 0
    for i in range(m):
        for j in range(n):
            s = str(a[i][j])
            l = len(s)
            if l > maxSize:
                maxSize = l
                
    txt = ""
    # Print rows of matrix
    for i in range(m):
        if i > 0:
            txt += '\n' # Row delimiter
        # Print i-th row of matrix
        txt += '['          # Beginning of row
        for j in range(n):
            if j > 0:
                txt += ' '  # Element delimeter
            s = str(a[i][j])
            l = len(s)
            if l < maxSize:
                txt += ' '*(maxSize - l) # Padding
            txt += s
        txt += ']'          # End of row
    # txt += '\n'
    return txt        
            
def determinantOfRationalMatrix(a):
    (b, rank) = echelonFormOfRationalMatrix(a)
    d = Fraction(1)
    m = len(b)          # Number of rows
    for i in range(m):
        d *= b[i][i]    # Multiply d by diagonal element
    return d

def multiplyMatrices(a, b):
    if len(a) == 0 or len(a[0]) == 0:
        raise ValueError("empty matrix a") 
    if len(b) == 0 or len(b[0]) == 0:
        raise ValueError("empty matrix b")
    rows_a = len(a)
    cols_a = len(a[0])
    rows_b = len(b)
    cols_b = len(b[0])
    if cols_a != rows_b:
        raise ValueError("matrices cannot be multiplied")
    
    # Create a zero matrix of size rows_a * cols_b
    zeroLine = [0]*cols_b
    c = [ zeroLine.copy() for i in range(rows_a) ]
    for i in range(rows_a):
        for j in range(cols_b):
            for k in range(cols_a):
                c[i][j] += a[i][k]*b[k][j]
    return c            

def echelonFormOfRealMatrix(a, eps=1e-8):
    '''For a matrix a, compute its row echelon matrix and the rank.
       Returns pair: (Echelon form of matrix, rank of matrix)'''
    b = copyRealMatrix(a)
    m = len(b)      # Number of rows
    n = len(b[0])   # Number of columns
    
    i = 0; j = 0
    while i < m and j < n:
        # Find element with maximal absolute value in j-th column, starting
        #      from line i
        imax = (-1)
        maxelem = 0.0;
        for k in range(i, m):
            if abs(b[k][j]) > maxelem:
                imax = k
                maxelem = abs(b[k][j])
        if maxelem <= eps:
            # Clear and skip a zero column
            for k in range(i, m):
                b[k][j] = 0.0
            j += 1      # Go to the next column
            continue
            
        assert(abs(b[imax][j]) > eps)
        
        # Swap rows i and imax and change a sign of one row
        if imax != i:
            swapMatrixRows(b, i, imax)
        r = b[i][j] 
        for k in range(i+1, m):
            c = (-b[k][j])/r
            addMatrixLines(b, k, i, c)
            b[k][j] = 0.0   # replace very little element by strict zero
        i += 1; j += 1
    return (b, i)

def showRealMatrix(a):
    # First define a maximal size of matrix elements
    m = len(a)      # Number of rows
    n = len(a[0])   # Number of columns
    assert(m > 0 and n > 0)
    maxSize = 0
    for i in range(m):
        for j in range(n):
            # s = str(a[i][j])
            s = "{0:12.4f}".format(a[i][j])
            l = len(s)
            if l > maxSize:
                maxSize = l
                
    txt = ""
    # Print rows of matrix
    for i in range(m):
        if i > 0:
            txt += '\n' # Row delimiter
        # Print i-th row of matrix
        txt += '['          # Beginning of row
        for j in range(n):
            if j > 0:
                txt += ' '  # Element delimeter
            # s = str(a[i][j])
            s = "{0:12.4f}".format(a[i][j])
            l = len(s)
            if l < maxSize:
                txt += ' '*(maxSize - l) # Padding
            txt += s
        txt += ']'          # End of row
    # txt += '\n'
    return txt        

def determinantOfRealMatrix(a):
    (b, rank) = echelonFormOfRealMatrix(a)
    d = 1.0
    m = len(b)          # Number of rows
    for i in range(m):
        d *= b[i][i]    # Multiply d by diagonal element
    return d