


'''simple docstring'''






from __future__ import annotations





def      UpperCAmelCase      (		lowerCamelCase_  :Optional[int]				,      lowerCamelCase_  :int ):







		'''simple docstring'''
		# Checks if the entire collection has been sorted
		if len(lowercase__ ) <= 1 or n <= 1:
				return

		insert_next(lowercase__				,      n - 1 )
		rec_insertion_sort(lowercase__				,      n - 1 )





def      UpperCAmelCase      (		lowerCamelCase_  :Union[str, Any]				,      lowerCamelCase_  :str ):







		'''simple docstring'''
		# Checks order between adjacent elements
		if index >= len(lowercase__ ) or collection[index - 1] <= collection[index]:
				return

		# Swaps adjacent elements since they are not in ascending order
		snake_case_       ,      snake_case_		:							Tuple			       =						(
		    collection[index],
		    collection[index - 1],
		)

		insert_next(lowercase__				,      index + 1 )


if __name__ == "__main__":
							__A	:	Optional[int]     =     input('Enter integers separated by spaces: ')
							__A	:	List[Any]     =     [int(num) for num in numbers.split()]
							rec_insertion_sort(number_list, len(number_list))
							print(number_list)



'''simple docstring'''






from __future__ import annotations

import math





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		if len(lowerCamelCase_ ) != 2 or len(a[0] ) != 2 or len(lowerCamelCase_ ) != 2 or len(b[0] ) != 2:
				raise Exception("""Matrices are not 2x2""" )
		snake_case_		:							Tuple			       =						[
		    [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      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		return [
		    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
		    for row in range(len(lowerCamelCase_ ) )
		]





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		return [
		    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
		    for row in range(len(lowerCamelCase_ ) )
		]





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







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

		snake_case_		:							Optional[int]			       =						len(lowerCamelCase_ )
		snake_case_		:							List[str]			       =						matrix_length // 2

		snake_case_		:							Union[str, Any]			       =						[[a[i][j] for j in range(lowerCamelCase_				,      lowerCamelCase_ )] for i in range(lowerCamelCase_ )]
		snake_case_		:							Dict			       =						[
		    [a[i][j] for j in range(lowerCamelCase_				,      lowerCamelCase_ )] for i in range(lowerCamelCase_				,      lowerCamelCase_ )
		]

		snake_case_		:							str			       =						[[a[i][j] for j in range(lowerCamelCase_ )] for i in range(lowerCamelCase_ )]
		snake_case_		:							Dict			       =						[[a[i][j] for j in range(lowerCamelCase_ )] for i in range(lowerCamelCase_				,      lowerCamelCase_ )]

		return top_left, top_right, bot_left, bot_right





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







		'''simple docstring'''
		return len(lowerCamelCase_ ), len(matrix[0] )





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







		'''simple docstring'''
		print("""\n""".join(str(lowerCamelCase_ ) for line in matrix ) )





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		if matrix_dimensions(lowerCamelCase_ ) == (2, 2):
				return default_matrix_multiplication(lowerCamelCase_				,      lowerCamelCase_ )

		snake_case_       ,      snake_case_       ,      snake_case_       ,      snake_case_		:							Any			       =						split_matrix(lowerCamelCase_ )
		snake_case_       ,      snake_case_       ,      snake_case_       ,      snake_case_		:							List[Any]			       =						split_matrix(lowerCamelCase_ )

		snake_case_		:							Any			       =						actual_strassen(lowerCamelCase_				,      matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							str			       =						actual_strassen(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )
		snake_case_		:							str			       =						actual_strassen(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )
		snake_case_		:							List[str]			       =						actual_strassen(lowerCamelCase_				,      matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							Optional[int]			       =						actual_strassen(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      matrix_addition(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							Dict			       =						actual_strassen(matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ )				,      matrix_addition(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							int			       =						actual_strassen(matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ )				,      matrix_addition(lowerCamelCase_				,      lowerCamelCase_ ) )

		snake_case_		:							List[Any]			       =						matrix_addition(matrix_subtraction(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )				,      lowerCamelCase_ )
		snake_case_		:							List[Any]			       =						matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )
		snake_case_		:							str			       =						matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )
		snake_case_		:							Any			       =						matrix_subtraction(matrix_subtraction(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )				,      lowerCamelCase_ )

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





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		if matrix_dimensions(lowerCamelCase_ )[1] != matrix_dimensions(lowerCamelCase_ )[0]:
				snake_case_		:							Optional[int]			       =						(
				    """Unable to multiply these matrices, please check the dimensions.\n"""
				    F'''Matrix A: {matrixa}\n'''
				    F'''Matrix B: {matrixa}'''
				)
				raise Exception(lowerCamelCase_ )
		snake_case_		:							Tuple			       =						matrix_dimensions(lowerCamelCase_ )
		snake_case_		:							Union[str, Any]			       =						matrix_dimensions(lowerCamelCase_ )

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

		snake_case_		:							int			       =						max(*lowerCamelCase_				,      *lowerCamelCase_ )
		snake_case_		:							Union[str, Any]			       =						int(math.pow(2				,      math.ceil(math.loga(lowerCamelCase_ ) ) ) )
		snake_case_		:							Dict			       =						matrixa
		snake_case_		:							Optional[int]			       =						matrixa

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

		snake_case_		:							Dict			       =						actual_strassen(lowerCamelCase_				,      lowerCamelCase_ )

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


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