



from functools import reduce

UpperCAmelCase_		 =					(
    """73167176531330624919225119674426574742355349194934"""
    """96983520312774506326239578318016984801869478851843"""
    """85861560789112949495459501737958331952853208805511"""
    """12540698747158523863050715693290963295227443043557"""
    """66896648950445244523161731856403098711121722383113"""
    """62229893423380308135336276614282806444486645238749"""
    """30358907296290491560440772390713810515859307960866"""
    """70172427121883998797908792274921901699720888093776"""
    """65727333001053367881220235421809751254540594752243"""
    """52584907711670556013604839586446706324415722155397"""
    """53697817977846174064955149290862569321978468622482"""
    """83972241375657056057490261407972968652414535100474"""
    """82166370484403199890008895243450658541227588666881"""
    """16427171479924442928230863465674813919123162824586"""
    """17866458359124566529476545682848912883142607690042"""
    """24219022671055626321111109370544217506941658960408"""
    """07198403850962455444362981230987879927244284909188"""
    """84580156166097919133875499200524063689912560717606"""
    """05886116467109405077541002256983155200055935729725"""
    """71636269561882670428252483600823257530420752963450"""
)

def 	SCREAMING_SNAKE_CASE_							(	_snake_case	:str = N				)  ->     int:
   return max(
       # mypy cannot properly interpret reduce
       int(reduce(lambda _snake_case	,   _snake_case				: str(int(_snake_case				) * int(_snake_case				)				)	,   n[i : i + 13]				)				)
       for i in range(len(_snake_case				) - 12				)				)


if __name__ == "__main__":
   print(f'{solution() = }')











from __future__ import annotations

import math
def 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase) ->			list:
      """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')
      UpperCamelCase					       =  [
          [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 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase) ->			Union[str, 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 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase) ->			Optional[int]:
      """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 		lowercase__  (				_UpperCamelCase) ->			tuple[list, list, list, list]:
      """simple docstring"""

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

      UpperCamelCase					       =  len(_UpperCamelCase)
      UpperCamelCase					       =  matrix_length // 2

      UpperCamelCase					       =  [[a[i][j] for j in range(_UpperCamelCase       ,							_UpperCamelCase)] for i in range(_UpperCamelCase)]
      UpperCamelCase					       =  [
          [a[i][j] for j in range(_UpperCamelCase       ,							_UpperCamelCase)] for i in range(_UpperCamelCase       ,							_UpperCamelCase)
      ]

      UpperCamelCase					       =  [[a[i][j] for j in range(_UpperCamelCase)] for i in range(_UpperCamelCase)]
      UpperCamelCase					       =  [[a[i][j] for j in range(_UpperCamelCase)] for i in range(_UpperCamelCase       ,							_UpperCamelCase)]

      return top_left, top_right, bot_left, bot_right
def 		lowercase__  (				_UpperCamelCase) ->			tuple[int, int]:
      """simple docstring"""

      return len(_UpperCamelCase), len(matrix[0])
def 		lowercase__  (				_UpperCamelCase) ->			None:
      """simple docstring"""

      print('\n'.join(str(_UpperCamelCase) for line in matrix))
def 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase) ->			list:
      """simple docstring"""

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

      UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase					       =  split_matrix(_UpperCamelCase)
      UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase       ,  UpperCamelCase					       =  split_matrix(_UpperCamelCase)

      UpperCamelCase					       =  actual_strassen(_UpperCamelCase       ,							matrix_subtraction(_UpperCamelCase       ,							_UpperCamelCase))
      UpperCamelCase					       =  actual_strassen(matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)       ,							_UpperCamelCase)
      UpperCamelCase					       =  actual_strassen(matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)       ,							_UpperCamelCase)
      UpperCamelCase					       =  actual_strassen(_UpperCamelCase       ,							matrix_subtraction(_UpperCamelCase       ,							_UpperCamelCase))
      UpperCamelCase					       =  actual_strassen(matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)       ,							matrix_addition(_UpperCamelCase       ,							_UpperCamelCase))
      UpperCamelCase					       =  actual_strassen(matrix_subtraction(_UpperCamelCase       ,							_UpperCamelCase)       ,							matrix_addition(_UpperCamelCase       ,							_UpperCamelCase))
      UpperCamelCase					       =  actual_strassen(matrix_subtraction(_UpperCamelCase       ,							_UpperCamelCase)       ,							matrix_addition(_UpperCamelCase       ,							_UpperCamelCase))

      UpperCamelCase					       =  matrix_addition(matrix_subtraction(matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)       ,							_UpperCamelCase)       ,							_UpperCamelCase)
      UpperCamelCase					       =  matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)
      UpperCamelCase					       =  matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)
      UpperCamelCase					       =  matrix_subtraction(matrix_subtraction(matrix_addition(_UpperCamelCase       ,							_UpperCamelCase)       ,							_UpperCamelCase)       ,							_UpperCamelCase)

      # construct the new matrix from our 4 quadrants
      UpperCamelCase					       =  []
      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 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase) ->			list:
      """simple docstring"""

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

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

      UpperCamelCase					       =  max(*_UpperCamelCase       ,							*_UpperCamelCase)
      UpperCamelCase					       =  int(math.pow(2       ,							math.ceil(math.loga(_UpperCamelCase))))
      UpperCamelCase					       =  matrixa
      UpperCamelCase					       =  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)

      UpperCamelCase					       =  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__":
       __magic_name__   :  Optional[Any]        =							[
           [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],
       ]
       __magic_name__   :  List[str]        =							[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
       print(strassen(matrixa, matrixa))



