from fractions import *

def copyRationalMatrix(a):
    m = len(a)
    assert(m > 0)
    n = len(a[0])
    assert(n > 0)
    b = []
    for i in range(m):
        assert(len(a[i]) == n)
        row = [Fraction(a[i][j]) for j in range(n)]
        b.append(row)
    return b
    
def showRationalMatrix(a):
    res = ""
    m = len(a)
    n = len(a[0])
    maxLen = 0
    for i in range(m):
        for j in range(n):
            txt = str(a[i][j])
            l = len(txt)
            if l > maxLen:
                maxLen = l
    
    for i in range(m):
        if i > 0:
            res += '\n'     # Line delimiter
        res += '['
        for j in range(n):
            if j > 0:
                res += ' '  # Element delimiter
            txt = str(a[i][j])
            l = len(txt)
            for k in range(maxLen - l):
                res += ' '
            res += txt
        res += ']'
    return res
    
def swapMatrixRows(a, i, k):
    assert(0 <= i and i < len(a) and 0 <= k and k < len(a))
    if i == k:
        return
    n = len(a[i])
    assert(n == len(a[k]))
    for j in range(n):
        (a[i][j], a[k][j]) = (a[k][j], -a[i][j])
        
def addMatrixRows(a, k, i, r):
    assert(0 <= i and i < len(a) and 0 <= k and k < len(a))
    n = len(a[i])
    assert(len(a[k]) == n)
    for j in range(n):
        a[k][j] += a[i][j]*r
    
def echelonFormOfRationalMatrix(a):
    b = copyRationalMatrix(a)
    m = len(b)      # number of rows
    n = len(b[0])   # number of columns
    i = 0           # number of rows processed    
    j = 0           # number of columns processed
    while i < m and j < n:
        # 1. Looking for nonzero element in j-th column
        #    starting from i-th row
        iMax = i
        for k in range(i, m):
            if b[k][j] != 0:
                iMax = k
                break
        if b[iMax][j] == 0:
            # Zero column
            j += 1
            continue
            
        assert(b[iMax][j] != 0)
        if iMax != i:
            swapMatrixRows(b, i, iMax)
        assert(b[i][j] != 0)
                
        # 2. Annihilate elements of j-th column,
        #    starting from i+1-th row
        c = b[i][j]
        for k in range(i+1, m):
            addMatrixRows(b, k, i, -b[k][j]/c)
        i += 1
        j += 1    
    return (b, i)        

def copyRealMatrix(a):
    m = len(a)
    assert(m > 0)
    n = len(a[0])
    assert(n > 0)
    b = []
    for i in range(m):
        assert(len(a[i]) == n)
        row = [float(a[i][j]) for j in range(n)]
        b.append(row)
    return b
    
def showRealMatrix(a):
    res = ""
    m = len(a)
    n = len(a[0])
    maxLen = 0
    for i in range(m):
        for j in range(n):
            # txt = str(a[i][j])
            txt = "{0:.4f}".format(float(a[i][j]))
            l = len(txt)
            if l > maxLen:
                maxLen = l
    
    for i in range(m):
        if i > 0:
            res += '\n'     # Line delimiter
        res += '['
        for j in range(n):
            if j > 0:
                res += ' '  # Element delimiter
            # txt = str(a[i][j])
            txt = "{0:.4f}".format(float(a[i][j]))
            l = len(txt)
            for k in range(maxLen - l):
                res += ' '
            res += txt
        res += ']'
    return res

def echelonFormOfRealMatrix(a, eps = 1e-8):
    b = copyRealMatrix(a)
    m = len(b)      # number of rows
    n = len(b[0])   # number of columns
    i = 0           # number of rows processed    
    j = 0           # number of columns processed
    while i < m and j < n:
        # 1. Looking for element in j-th column with maximal abs. value,
        #    starting from i-th row
        iMax = i
        vMax = abs(b[i][j])
        for k in range(i + 1, m):
            if abs(b[k][j]) > vMax:
                iMax = k; vMax = abs(b[k][j])
        if vMax <= eps:
            # Zero column
            # Replace small numbers by zeroes
            for k in range(i, m):
                b[k][j] = 0.0
            j += 1
            continue
            
        assert(abs(b[iMax][j]) > eps)
        if iMax != i:
            swapMatrixRows(b, i, iMax)
        assert(abs(b[i][j]) > eps)
                
        # 2. Annihilate elements of j-th column,
        #    starting from i+1-th row
        c = b[i][j]
        for k in range(i+1, m):
            addMatrixRows(b, k, i, -b[k][j]/c);
            b[k][j] = 0.0
        i += 1
        j += 1    
    return (b, i)        

def determinantOfRationalMatrix(a):
    if len(a) == 0 or len(a) != len(a[0]):
        raise ValueError("Determinant of non-square matrix")
    (b, rank) = echelonFormOfRationalMatrix(a)
    d = b[0][0]
    for i in range(1, len(b)):
        d *= b[i][i]
    return d
    
def determinantOfRealMatrix(a, eps = 1e-8):
    if len(a) == 0 or len(a) != len(a[0]):
        raise ValueError("Determinant of non-square matrix")
    (b, rank) = echelonFormOfRealMatrix(a, eps)
    d = b[0][0]
    for i in range(1, len(b)):
        d *= b[i][i]
    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