

from __future__ import annotations

import math







def 						lowerCamelCase__      ( __A    :List[Any]	,__A    :Union[str, Any]		):


       """simple docstring"""




       if len(UpperCamelCase_		) != 2 or len(a[0]		) != 2 or len(UpperCamelCase_		) != 2 or len(b[0]		) != 2:
              raise Exception("""Matrices are not 2x2"""		)
       __snake_case       	=							[
           [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
           [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
       ]
       return new_matrix







def 						lowerCamelCase__      ( __A    :Union[str, Any]	,__A    :Dict		):


       """simple docstring"""




       return [
           [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]		)		)]
           for row in range(len(UpperCamelCase_		)		)
       ]







def 						lowerCamelCase__      ( __A    :List[Any]	,__A    :List[Any]		):


       """simple docstring"""




       return [
           [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]		)		)]
           for row in range(len(UpperCamelCase_		)		)
       ]







def 						lowerCamelCase__      ( __A    :Optional[int]		):


       """simple docstring"""




       if len(UpperCamelCase_		) % 2 != 0 or len(a[0]		) % 2 != 0:
              raise Exception("""Odd matrices are not supported!"""		)

       __snake_case       	=							len(UpperCamelCase_		)
       __snake_case       	=							matrix_length // 2

       __snake_case       	=							[[a[i][j] for j in range(UpperCamelCase_	,UpperCamelCase_		)] for i in range(UpperCamelCase_		)]
       __snake_case       	=							[
           [a[i][j] for j in range(UpperCamelCase_	,UpperCamelCase_		)] for i in range(UpperCamelCase_	,UpperCamelCase_		)
       ]

       __snake_case       	=							[[a[i][j] for j in range(UpperCamelCase_		)] for i in range(UpperCamelCase_		)]
       __snake_case       	=							[[a[i][j] for j in range(UpperCamelCase_		)] for i in range(UpperCamelCase_	,UpperCamelCase_		)]

       return top_left, top_right, bot_left, bot_right







def 						lowerCamelCase__      ( __A    :str		):


       """simple docstring"""




       return len(UpperCamelCase_		), len(matrix[0]		)







def 						lowerCamelCase__      ( __A    :Optional[int]		):


       """simple docstring"""




       print("""\n""".join(str(UpperCamelCase_		) for line in matrix		)		)







def 						lowerCamelCase__      ( __A    :Union[str, Any]	,__A    :List[str]		):


       """simple docstring"""




       if matrix_dimensions(UpperCamelCase_		) == (2, 2):
              return default_matrix_multiplication(UpperCamelCase_	,UpperCamelCase_		)

       __snake_case	,    __snake_case	,    __snake_case	,    __snake_case       	=							split_matrix(UpperCamelCase_		)
       __snake_case	,    __snake_case	,    __snake_case	,    __snake_case       	=							split_matrix(UpperCamelCase_		)

       __snake_case       	=							actual_strassen(UpperCamelCase_	,matrix_subtraction(UpperCamelCase_	,UpperCamelCase_		)		)
       __snake_case       	=							actual_strassen(matrix_addition(UpperCamelCase_	,UpperCamelCase_		)	,UpperCamelCase_		)
       __snake_case       	=							actual_strassen(matrix_addition(UpperCamelCase_	,UpperCamelCase_		)	,UpperCamelCase_		)
       __snake_case       	=							actual_strassen(UpperCamelCase_	,matrix_subtraction(UpperCamelCase_	,UpperCamelCase_		)		)
       __snake_case       	=							actual_strassen(matrix_addition(UpperCamelCase_	,UpperCamelCase_		)	,matrix_addition(UpperCamelCase_	,UpperCamelCase_		)		)
       __snake_case       	=							actual_strassen(matrix_subtraction(UpperCamelCase_	,UpperCamelCase_		)	,matrix_addition(UpperCamelCase_	,UpperCamelCase_		)		)
       __snake_case       	=							actual_strassen(matrix_subtraction(UpperCamelCase_	,UpperCamelCase_		)	,matrix_addition(UpperCamelCase_	,UpperCamelCase_		)		)

       __snake_case       	=							matrix_addition(matrix_subtraction(matrix_addition(UpperCamelCase_	,UpperCamelCase_		)	,UpperCamelCase_		)	,UpperCamelCase_		)
       __snake_case       	=							matrix_addition(UpperCamelCase_	,UpperCamelCase_		)
       __snake_case       	=							matrix_addition(UpperCamelCase_	,UpperCamelCase_		)
       __snake_case       	=							matrix_subtraction(matrix_subtraction(matrix_addition(UpperCamelCase_	,UpperCamelCase_		)	,UpperCamelCase_		)	,UpperCamelCase_		)

       # construct the new matrix from our 4 quadrants
       __snake_case       	=							[]
       for i in range(len(UpperCamelCase_		)		):
              new_matrix.append(top_left[i] + top_right[i]		)
       for i in range(len(UpperCamelCase_		)		):
              new_matrix.append(bot_left[i] + bot_right[i]		)
       return new_matrix







def 						lowerCamelCase__      ( __A    :Any	,__A    :Tuple		):


       """simple docstring"""




       if matrix_dimensions(UpperCamelCase_		)[1] != matrix_dimensions(UpperCamelCase_		)[0]:
              __snake_case       	=							(
                  """Unable to multiply these matrices, please check the dimensions.\n"""
                  F'Matrix A: {matrixa}\n'
                  F'Matrix B: {matrixa}'
              )
              raise Exception(UpperCamelCase_		)
       __snake_case       	=							matrix_dimensions(UpperCamelCase_		)
       __snake_case       	=							matrix_dimensions(UpperCamelCase_		)

       if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
              return [matrixa, matrixa]

       __snake_case       	=							max(*UpperCamelCase_	,*UpperCamelCase_		)
       __snake_case       	=							int(math.pow(2	,math.ceil(math.loga(UpperCamelCase_		)		)		)		)
       __snake_case       	=							matrixa
       __snake_case       	=							matrixa

       # Adding zeros to the matrices so that the arrays dimensions are the same and also
       # power of 2
       for i in range(0	,UpperCamelCase_		):
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]	,UpperCamelCase_		):
                            new_matrixa[i].append(0		)
              else:
                     new_matrixa.append([0] * maxim		)
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]	,UpperCamelCase_		):
                            new_matrixa[i].append(0		)
              else:
                     new_matrixa.append([0] * maxim		)

       __snake_case       	=							actual_strassen(UpperCamelCase_	,UpperCamelCase_		)

       # Removing the additional zeros
       for i in range(0	,UpperCamelCase_		):
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]	,UpperCamelCase_		):
                            final_matrix[i].pop()
              else:
                     final_matrix.pop()
       return final_matrix


if __name__ == "__main__":
    UpperCamelCase__		 =     [
        [2, 3, 4, 5],
        [6, 4, 3, 1],
        [2, 3, 6, 7],
        [3, 1, 2, 4],
        [2, 3, 4, 5],
        [6, 4, 3, 1],
        [2, 3, 6, 7],
        [3, 1, 2, 4],
        [2, 3, 4, 5],
        [6, 2, 3, 1],
    ]
    UpperCamelCase__		 =     [[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
    print(strassen(matrixa, matrixa))


_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    8_0_0,
    7_9_9,
    6_0_0,
    5_9_9,
    5_0_0,
    4_0_0,
    3_9_9,
    3_7_7,
    3_5_5,
    3_3_3,
    3_1_1,
    2_8_8,
    2_6_6,
    2_4_4,
    2_2_2,
    2_0_0,
    1_9_9,
    1_7_7,
    1_5_5,
    1_3_3,
    1_1_1,
    8_8,
    6_6,
    4_4,
    2_2,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_7_6,
    9_5_2,
    9_2_8,
    9_0_5,
    8_8_2,
    8_5_8,
    8_5_7,
    8_1_0,
    7_6_2,
    7_1_5,
    7_1_4,
    5_7_2,
    4_2_9,
    4_2_8,
    2_8_6,
    2_8_5,
    2_3_8,
    1_9_0,
    1_4_3,
    1_4_2,
    1_1_8,
    9_5,
    7_1,
    4_7,
    2_4,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_8_8,
    9_7_7,
    9_6_6,
    9_5_5,
    9_4_4,
    9_3_3,
    9_2_2,
    9_1_1,
    9_0_0,
    8_9_9,
    8_7_9,
    8_5_9,
    8_4_0,
    8_2_0,
    8_0_0,
    7_9_9,
    7_6_6,
    7_3_3,
    7_0_0,
    6_9_9,
    6_5_0,
    6_0_0,
    5_9_9,
    5_0_0,
    4_9_9,
    4_0_0,
    3_9_9,
    3_5_0,
    3_0_0,
    2_9_9,
    2_6_6,
    2_3_3,
    2_0_0,
    1_9_9,
    1_7_9,
    1_5_9,
    1_4_0,
    1_2_0,
    1_0_0,
    9_9,
    8_8,
    7_7,
    6_6,
    5_5,
    4_4,
    3_3,
    2_2,
    1_1,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_9_5,
    9_9_2,
    9_8_9,
    9_8_5,
    9_8_1,
    9_7_8,
    9_7_5,
    9_7_1,
    9_6_7,
    9_6_4,
    9_6_1,
    9_5_7,
    9_5_6,
    9_5_1,
    9_4_7,
    9_4_2,
    9_3_7,
    9_3_3,
    9_2_8,
    9_2_3,
    9_1_9,
    9_1_4,
    9_1_3,
    9_0_8,
    9_0_3,
    8_9_7,
    8_9_2,
    8_8_7,
    8_8_1,
    8_7_6,
    8_7_1,
    8_7_0,
    8_6_4,
    8_5_8,
    8_5_2,
    8_4_6,
    8_4_0,
    8_3_4,
    8_2_8,
    8_2_7,
    8_2_0,
    8_1_3,
    8_0_6,
    7_9_9,
    7_9_2,
    7_8_5,
    7_8_4,
    7_7_7,
    7_7_0,
    7_6_3,
    7_5_6,
    7_4_9,
    7_4_2,
    7_4_1,
    7_3_3,
    7_2_4,
    7_1_6,
    7_0_7,
    6_9_9,
    6_9_8,
    6_8_8,
    6_7_7,
    6_6_6,
    6_5_6,
    6_5_5,
    6_4_5,
    6_3_4,
    6_2_3,
    6_1_3,
    6_1_2,
    5_9_8,
    5_8_4,
    5_7_0,
    5_6_9,
    5_5_5,
    5_4_1,
    5_2_7,
    5_2_6,
    5_0_5,
    4_8_4,
    4_8_3,
    4_6_2,
    4_4_0,
    4_3_9,
    3_9_6,
    3_9_5,
    3_5_2,
    3_5_1,
    3_0_8,
    3_0_7,
    2_6_4,
    2_6_3,
    2_2_0,
    2_1_9,
    1_7_6,
    1_3_2,
    8_8,
    4_4,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_9_7,
    9_9_5,
    9_9_2,
    9_9_0,
    9_8_8,
    9_8_6,
    9_8_4,
    9_8_1,
    9_7_9,
    9_7_7,
    9_7_5,
    9_7_2,
    9_7_0,
    9_6_8,
    9_6_6,
    9_6_4,
    9_6_1,
    9_5_9,
    9_5_7,
    9_5_6,
    9_5_4,
    9_5_1,
    9_4_9,
    9_4_6,
    9_4_4,
    9_4_1,
    9_3_9,
    9_3_6,
    9_3_4,
    9_3_1,
    9_2_9,
    9_2_6,
    9_2_4,
    9_2_1,
    9_1_9,
    9_1_6,
    9_1_4,
    9_1_3,
    9_1_0,
    9_0_7,
    9_0_5,
    9_0_2,
    8_9_9,
    8_9_6,
    8_9_3,
    8_9_1,
    8_8_8,
    8_8_5,
    8_8_2,
    8_7_9,
    8_7_7,
    8_7_4,
    8_7_1,
    8_7_0,
    8_6_7,
    8_6_4,
    8_6_1,
    8_5_8,
    8_5_5,
    8_5_2,
    8_4_9,
    8_4_6,
    8_4_3,
    8_4_0,
    8_3_7,
    8_3_4,
    8_3_1,
    8_2_8,
    8_2_7,
    8_2_4,
    8_2_1,
    8_1_7,
    8_1_4,
    8_1_1,
    8_0_8,
    8_0_4,
    8_0_1,
    7_9_8,
    7_9_5,
    7_9_1,
    7_8_8,
    7_8_5,
    7_8_4,
    7_8_0,
    7_7_7,
    7_7_4,
    7_7_0,
    7_6_6,
    7_6_3,
    7_6_0,
    7_5_6,
    7_5_2,
    7_4_9,
    7_4_6,
    7_4_2,
    7_4_1,
    7_3_7,
    7_3_3,
    7_3_0,
    7_2_6,
    7_2_2,
    7_1_8,
    7_1_4,
    7_1_0,
    7_0_7,
    7_0_3,
    6_9_9,
    6_9_8,
    6_9_4,
    6_9_0,
    6_8_5,
    6_8_1,
    6_7_7,
    6_7_3,
    6_6_9,
    6_6_4,
    6_6_0,
    6_5_6,
    6_5_5,
    6_5_0,
    6_4_6,
    6_4_1,
    6_3_6,
    6_3_2,
    6_2_7,
    6_2_2,
    6_1_8,
    6_1_3,
    6_1_2,
    6_0_7,
    6_0_2,
    5_9_6,
    5_9_1,
    5_8_6,
    5_8_0,
    5_7_5,
    5_7_0,
    5_6_9,
    5_6_3,
    5_5_7,
    5_5_1,
    5_4_5,
    5_3_9,
    5_3_3,
    5_2_7,
    5_2_6,
    5_1_9,
    5_1_2,
    5_0_5,
    4_9_8,
    4_9_1,
    4_8_4,
    4_8_3,
    4_7_4,
    4_6_6,
    4_5_7,
    4_4_9,
    4_4_0,
    4_3_9,
    4_2_8,
    4_1_8,
    4_0_7,
    3_9_6,
    3_9_5,
    3_8_1,
    3_6_6,
    3_5_2,
    3_5_1,
    3_3_0,
    3_0_8,
    3_0_7,
    2_8_6,
    2_6_4,
    2_6_3,
    2_4_2,
    2_2_0,
    2_1_9,
    1_7_6,
    1_7_5,
    1_3_2,
    1_3_1,
    8_8,
    4_4,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_9_1,
    9_8_2,
    9_7_4,
    9_6_6,
    9_5_8,
    9_5_0,
    9_4_1,
    9_3_3,
    9_2_5,
    9_1_6,
    9_0_8,
    9_0_0,
    8_9_9,
    8_7_4,
    8_5_0,
    8_2_5,
    8_0_0,
    7_9_9,
    7_0_0,
    6_0_0,
    5_0_0,
    4_0_0,
    3_0_0,
    2_0_0,
    1_0_0,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_9_2,
    9_8_5,
    9_7_8,
    9_7_1,
    9_6_4,
    9_5_7,
    9_4_9,
    9_4_2,
    9_3_5,
    9_2_8,
    9_2_1,
    9_1_4,
    9_0_7,
    9_0_0,
    8_9_9,
    8_7_9,
    8_5_9,
    8_4_0,
    8_2_0,
    8_0_0,
    7_9_9,
    7_6_6,
    7_3_3,
    7_0_0,
    6_9_9,
    6_5_0,
    6_0_0,
    5_9_9,
    5_0_0,
    4_9_9,
    4_0_0,
    3_9_9,
    3_0_0,
    2_9_9,
    2_0_0,
    1_9_9,
    1_0_0,
    9_9,
    0,
]

_SCREAMING_SNAKE_CASE 		=      [
    9_9_9,
    9_9_6,
    9_9_2,
    9_8_9,
    9_8_5,
    9_8_2,
    9_7_9,
    9_7_5,
    9_7_2,
    9_6_8,
    9_6_5,
    9_6_1,
    9_5_8,
    9_5_5,
    9_5_1,
    9_4_8,
    9_4_4,
    9_4_1,
    9_3_8,
    9_3_4,
    9_3_1,
    9_2_7,
    9_2_4,
    9_2_0,
    9_1_7,
    9_1_4,
    9_1_0,
    9_0_7,
    9_0_3,
    9_0_0,
    8_9_9,
    8_9_1,
    8_8_4,
    8_7_6,
    8_6_9,
    8_6_1,
    8_5_3,
    8_4_6,
    8_3_8,
    8_3_0,
    8_2_3,
    8_1_5,
    8_0_8,
    8_0_0,
    7_9_9,
    7_8_8,
    7_7_7,
    7_6_6,
    7_5_5,
    7_4_4,
    7_3_3,
    7_2_2,
    7_1_1,
    7_0_0,
    6_9_9,
    6_8_8,
    6_7_7,
    6_6_6,
    6_5_5,
    6_4_4,
    6_3_3,
    6_2_2,
    6_1_1,
    6_0_0,
    5_9_9,
    5_8_5,
    5_7_1,
    5_5_7,
    5_4_2,
    5_2_8,
    5_1_4,
    5_0_0,
    4_9_9,
    4_8_5,
    4_7_1,
    4_5_7,
    4_4_2,
    4_2_8,
    4_1_4,
    4_0_0,
    3_9_9,
    3_7_9,
    3_5_9,
    3_4_0,
    3_2_0,
    3_0_0,
    2_9_9,
    2_7_9,
    2_5_9,
    2_4_0,
    2_2_0,
    2_0_0,
    1_9_9,
    1_6_6,
    1_3_3,
    1_0_0,
    9_9,
    6_6,
    3_3,
    0,
]
