






"""simple docstring"""
from __future__ import annotations

import math






def       __UpperCamelCase						(		snake_case__ , snake_case__       ):
	if len(snake_case__       ) != 2 or len(a[0]       ) != 2 or len(snake_case__       ) != 2 or len(b[0]       ) != 2:
		raise Exception("""Matrices are not 2x2"""       )
	A_		:    Any						     = [
	    [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       __UpperCamelCase						(		snake_case__ , snake_case__       ):
	return [
	    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]       )       )]
	    for row in range(len(snake_case__       )       )
	]






def       __UpperCamelCase						(		snake_case__ , snake_case__       ):
	return [
	    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]       )       )]
	    for row in range(len(snake_case__       )       )
	]






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

	A_		:    int						     = len(snake_case__       )
	A_		:    Tuple						     = matrix_length // 2

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

	A_		:    Optional[int]						     = [[a[i][j] for j in range(snake_case__       )] for i in range(snake_case__       )]
	A_		:    List[Any]						     = [[a[i][j] for j in range(snake_case__       )] for i in range(snake_case__ , snake_case__       )]

	return top_left, top_right, bot_left, bot_right






def       __UpperCamelCase						(		snake_case__       ):
	return len(snake_case__       ), len(matrix[0]       )






def       __UpperCamelCase						(		snake_case__       ):
	print("""\n""".join(str(snake_case__       ) for line in matrix       )       )






def       __UpperCamelCase						(		snake_case__ , snake_case__       ):
	if matrix_dimensions(snake_case__       ) == (2, 2):
		return default_matrix_multiplication(snake_case__ , snake_case__       )

	A_     ,  A_     ,  A_     ,  A_		:    Dict						     = split_matrix(snake_case__       )
	A_     ,  A_     ,  A_     ,  A_		:    str						     = split_matrix(snake_case__       )

	A_		:    Union[str, Any]						     = actual_strassen(snake_case__ , matrix_subtraction(snake_case__ , snake_case__       )       )
	A_		:    Dict						     = actual_strassen(matrix_addition(snake_case__ , snake_case__       ) , snake_case__       )
	A_		:    Optional[int]						     = actual_strassen(matrix_addition(snake_case__ , snake_case__       ) , snake_case__       )
	A_		:    str						     = actual_strassen(snake_case__ , matrix_subtraction(snake_case__ , snake_case__       )       )
	A_		:    Any						     = actual_strassen(matrix_addition(snake_case__ , snake_case__       ) , matrix_addition(snake_case__ , snake_case__       )       )
	A_		:    str						     = actual_strassen(matrix_subtraction(snake_case__ , snake_case__       ) , matrix_addition(snake_case__ , snake_case__       )       )
	A_		:    List[Any]						     = actual_strassen(matrix_subtraction(snake_case__ , snake_case__       ) , matrix_addition(snake_case__ , snake_case__       )       )

	A_		:    Optional[int]						     = matrix_addition(matrix_subtraction(matrix_addition(snake_case__ , snake_case__       ) , snake_case__       ) , snake_case__       )
	A_		:    List[Any]						     = matrix_addition(snake_case__ , snake_case__       )
	A_		:    List[str]						     = matrix_addition(snake_case__ , snake_case__       )
	A_		:    int						     = matrix_subtraction(matrix_subtraction(matrix_addition(snake_case__ , snake_case__       ) , snake_case__       ) , snake_case__       )

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






def       __UpperCamelCase						(		snake_case__ , snake_case__       ):
	if matrix_dimensions(snake_case__       )[1] != matrix_dimensions(snake_case__       )[0]:
		A_		:    Optional[int]						     = (
		    """Unable to multiply these matrices, please check the dimensions.\n"""
		    F"""Matrix A: {matrixa}\n"""
		    F"""Matrix B: {matrixa}"""
		)
		raise Exception(snake_case__       )
	A_		:    Union[str, Any]						     = matrix_dimensions(snake_case__       )
	A_		:    Optional[int]						     = matrix_dimensions(snake_case__       )

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

	A_		:    Tuple						     = max(*snake_case__ , *snake_case__       )
	A_		:    Tuple						     = int(math.pow(2 , math.ceil(math.loga(snake_case__       )       )       )       )
	A_		:    List[str]						     = matrixa
	A_		:    List[str]						     = matrixa

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

	A_		:    Union[str, Any]						     = actual_strassen(snake_case__ , snake_case__       )

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


if __name__ == "__main__":
							_lowerCAmelCase       =				[
							    [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],
							]
							_lowerCAmelCase       =				[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
							print(strassen(matrixa, matrixa))









"""simple docstring"""
from __future__ import annotations






def       __UpperCamelCase						(		snake_case__ , snake_case__ = None , snake_case__ = None       ):
	if start is None:
		A_		:    Dict						     = 0

	if end is None:
		A_		:    Dict						     = len(snake_case__       ) - 1

	if start >= end:
		return

	A_		:    List[Any]						     = (start + end) // 2

	slowsort(snake_case__ , snake_case__ , snake_case__       )
	slowsort(snake_case__ , mid + 1 , snake_case__       )

	if sequence[end] < sequence[mid]:
		A_     ,  A_		:    Dict						     = sequence[mid], sequence[end]

	slowsort(snake_case__ , snake_case__ , end - 1       )


if __name__ == "__main__":
							from doctest import testmod

							testmod()

