def matrix_addition(A, B):
    # Check if matrices have the same size
    if len(A) != len(B) or len(A[0]) != len(B[0]):
        raise ValueError("Matrices must have the same size")
    # Initialize result matrix with zeros
    result = [[0 for col in range(len(A[0]))] for row in range(len(A))]
    # Add matrices element-wise
    for row in range(len(A)):
        for col in range(len(A[0])):
            result[row][col] = A[row][col] + B[row][col]
    return result
def matrix_subtraction(A, B):
    # Check if matrices have the same size
    if len(A) != len(B) or len(A[0]) != len(B[0]):
        raise ValueError("Matrices must have the same size")
    # Initialize result matrix with zeros
    result = [[0 for col in range(len(A[0]))] for row in range(len(A))]
    # Subtract matrices element-wise
    for row in range(len(A)):
        for col in range(len(A[0])):
            result[row][col] = A[row][col] - B[row][col]
    return result
def strassen(a, b):
    if len(a) == 1 and len(a[0]) == 1:
        return [[a[0][0] * b[0][0]]]
    # Check if matrices have the same size
    if len(a) != len(a[0]) or len(b) != len(b[0]) or len(a) != len(b):
        raise ValueError("Matrices must be square and of the same size")
    # Check if the size is a power of 2
    size = len(a)
    if size & (size - 1) != 0:
        raise ValueError("Matrix size must be a power of 2")
    # Function to divide a matrix into four submatrices
    def divide(matrix):
        size = len(matrix)
        mid = size // 2
        quad1 = [row[:mid] for row in matrix[:mid]]
        quad2 = [row[mid:] for row in matrix[:mid]]
        quad3 = [row[:mid] for row in matrix[mid:]]
        quad4 = [row[mid:] for row in matrix[mid:]]
        return quad1, quad2, quad3, quad4
    # Function to combine four submatrices into a single matrix
    def combine_submatrices(quad1, quad2, quad3, quad4):
        size = len(quad1)
        mid = size
        result = [[0 for _ in range(2 * mid)] for _ in range(2 * mid)]
        for i in range(mid):
            for j in range(mid):
                result[i][j] = quad1[i][j]
                result[i][j + mid] = quad2[i][j]
                result[i + mid][j] = quad3[i][j]
                result[i + mid][j + mid] = quad4[i][j]
        return result
    quad1_a, quad2_a, quad3_a, quad4_a = divide(a)
    quad1_b, quad2_b, quad3_b, quad4_b = divide(b)
    p1 = strassen(matrix_addition(quad1_a, quad4_a), matrix_addition(quad1_b, quad4_b))
    p2 = strassen(matrix_addition(quad3_a, quad4_a), quad1_b)
    p3 = strassen(quad1_a, matrix_subtraction(quad2_b, quad4_b))
    p4 = strassen(quad4_a, matrix_subtraction(quad3_b, quad1_b))
    p5 = strassen(matrix_addition(quad1_a, quad2_a), quad4_b)
    p6 = strassen(matrix_subtraction(quad3_a, quad1_a), matrix_addition(quad1_b, quad2_b))
    p7 = strassen(matrix_subtraction(quad2_a, quad4_a), matrix_addition(quad3_b, quad4_b))
    final_quad1 = matrix_subtraction(
        matrix_addition(p1, p4),
        matrix_addition(
            matrix_subtraction(
                matrix_addition(p5, p7),
                p2
            ),
            p6
        )
    )
    final_quad2 = matrix_addition(p3, p5)
    final_quad3 = matrix_addition(p2, p4)
    final_quad4 = matrix_subtraction(
        matrix_addition(p1, p3),
        matrix_addition(
            matrix_subtraction(p5, p2),
            p7
        )
    )
    return combine_submatrices(final_quad1, final_quad2, final_quad3, final_quad4)
A = [[1, 2, 3, 4],
     [5, 6, 7, 8],
     [9, 10, 11, 12],
     [13, 14, 15, 16]]
B = [[17, 18, 19, 20],
     [21, 22, 23, 24],
     [25, 26, 27, 28],
     [29, 30, 31, 32]]
result = strassen(A, B)
for row in result:
    print(row)