





from __future__ import annotations

import math


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase )			->     list:
    if len(_UpperCAmelCase ) != 2 or len(a[0] ) != 2 or len(_UpperCAmelCase ) != 2 or len(b[0] ) != 2:
        raise Exception('Matrices are not 2x2' )
    lowerCamelCase__    :      Optional[int]					 =		[
        [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        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase )			->     Optional[Any]:
    return [
        [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
        for row in range(len(_UpperCAmelCase ) )
    ]


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase )			->     int:
    return [
        [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
        for row in range(len(_UpperCAmelCase ) )
    ]


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     tuple[list, list, list, list]:
    if len(_UpperCAmelCase ) % 2 != 0 or len(a[0] ) % 2 != 0:
        raise Exception('Odd matrices are not supported!' )

    lowerCamelCase__    :      List[str]					 =		len(_UpperCAmelCase )
    lowerCamelCase__    :      List[str]					 =		matrix_length // 2

    lowerCamelCase__    :      Union[str, Any]					 =		[[a[i][j] for j in range(_UpperCAmelCase						,	_UpperCAmelCase )] for i in range(_UpperCAmelCase )]
    lowerCamelCase__    :      Optional[int]					 =		[
        [a[i][j] for j in range(_UpperCAmelCase						,	_UpperCAmelCase )] for i in range(_UpperCAmelCase						,	_UpperCAmelCase )
    ]

    lowerCamelCase__    :      List[Any]					 =		[[a[i][j] for j in range(_UpperCAmelCase )] for i in range(_UpperCAmelCase )]
    lowerCamelCase__    :      str					 =		[[a[i][j] for j in range(_UpperCAmelCase )] for i in range(_UpperCAmelCase						,	_UpperCAmelCase )]

    return top_left, top_right, bot_left, bot_right


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     tuple[int, int]:
    return len(_UpperCAmelCase ), len(matrix[0] )


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     None:
    print('\n'.join(str(_UpperCAmelCase ) for line in matrix ) )


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase )			->     list:
    if matrix_dimensions(_UpperCAmelCase ) == (2, 2):
        return default_matrix_multiplication(_UpperCAmelCase						,	_UpperCAmelCase )

    lowerCamelCase__ ,							lowerCamelCase__ ,							lowerCamelCase__ ,							lowerCamelCase__    :      Union[str, Any]					 =		split_matrix(_UpperCAmelCase )
    lowerCamelCase__ ,							lowerCamelCase__ ,							lowerCamelCase__ ,							lowerCamelCase__    :      str					 =		split_matrix(_UpperCAmelCase )

    lowerCamelCase__    :      List[Any]					 =		actual_strassen(_UpperCAmelCase						,	matrix_subtraction(_UpperCAmelCase						,	_UpperCAmelCase ) )
    lowerCamelCase__    :      Tuple					 =		actual_strassen(matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )						,	_UpperCAmelCase )
    lowerCamelCase__    :      Optional[int]					 =		actual_strassen(matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )						,	_UpperCAmelCase )
    lowerCamelCase__    :      Optional[int]					 =		actual_strassen(_UpperCAmelCase						,	matrix_subtraction(_UpperCAmelCase						,	_UpperCAmelCase ) )
    lowerCamelCase__    :      Optional[Any]					 =		actual_strassen(matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )						,	matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase ) )
    lowerCamelCase__    :      List[Any]					 =		actual_strassen(matrix_subtraction(_UpperCAmelCase						,	_UpperCAmelCase )						,	matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase ) )
    lowerCamelCase__    :      Union[str, Any]					 =		actual_strassen(matrix_subtraction(_UpperCAmelCase						,	_UpperCAmelCase )						,	matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase ) )

    lowerCamelCase__    :      Dict					 =		matrix_addition(matrix_subtraction(matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )						,	_UpperCAmelCase )						,	_UpperCAmelCase )
    lowerCamelCase__    :      Any					 =		matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )
    lowerCamelCase__    :      Tuple					 =		matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )
    lowerCamelCase__    :      int					 =		matrix_subtraction(matrix_subtraction(matrix_addition(_UpperCAmelCase						,	_UpperCAmelCase )						,	_UpperCAmelCase )						,	_UpperCAmelCase )

    # construct the new matrix from our 4 quadrants
    lowerCamelCase__    :      Dict					 =		[]
    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        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase )			->     list:
    if matrix_dimensions(_UpperCAmelCase )[1] != matrix_dimensions(_UpperCAmelCase )[0]:
        lowerCamelCase__    :      Any					 =		(
            'Unable to multiply these matrices, please check the dimensions.\n'
            F"""Matrix A: {matrixa}\n"""
            F"""Matrix B: {matrixa}"""
        )
        raise Exception(_UpperCAmelCase )
    lowerCamelCase__    :      Union[str, Any]					 =		matrix_dimensions(_UpperCAmelCase )
    lowerCamelCase__    :      Optional[int]					 =		matrix_dimensions(_UpperCAmelCase )

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

    lowerCamelCase__    :      Optional[Any]					 =		max(*_UpperCAmelCase						,	*_UpperCAmelCase )
    lowerCamelCase__    :      Dict					 =		int(math.pow(2						,	math.ceil(math.loga(_UpperCAmelCase ) ) ) )
    lowerCamelCase__    :      str					 =		matrixa
    lowerCamelCase__    :      List[Any]					 =		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 )

    lowerCamelCase__    :      int					 =		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				:       List[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],
    ]
    _UpperCAmelCase				:       Tuple	   =				[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
    print(strassen(matrixa, matrixa))












"""simple docstring"""
from typing import Any



def      __lowerCamelCase   (							a_     :		list							)			->      list[Any]:
      if not input_list:
            return []
      __SCREAMING_SNAKE_CASE   :int						=  [input_list.count(a_							) for value in input_list]
      __SCREAMING_SNAKE_CASE   :str						=  max(a_							)  # Gets the maximum count in the input list.
      # Gets values of modes
      return sorted({input_list[i] for i, value in enumerate(a_							) if value == y}							)


if __name__ == "__main__":
  import doctest

  doctest.testmod()