


from __future__ import annotations

import math







def  __snake_case       (   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'	)
		A					       = [
		    [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  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		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  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		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  __snake_case       (   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!'	)

		A					       = len(UpperCamelCase__	)
		A					       = matrix_length // 2

		A					       = [[a[i][j] for j in range(UpperCamelCase__ ,			UpperCamelCase__	)] for i in range(UpperCamelCase__	)]
		A					       = [
		    [a[i][j] for j in range(UpperCamelCase__ ,			UpperCamelCase__	)] for i in range(UpperCamelCase__ ,			UpperCamelCase__	)
		]

		A					       = [[a[i][j] for j in range(UpperCamelCase__	)] for i in range(UpperCamelCase__	)]
		A					       = [[a[i][j] for j in range(UpperCamelCase__	)] for i in range(UpperCamelCase__ ,			UpperCamelCase__	)]

		return top_left, top_right, bot_left, bot_right







def  __snake_case       (   UpperCamelCase__	)      ->		tuple[int, int]:







		"""simple docstring"""





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







def  __snake_case       (   UpperCamelCase__	)      ->		None:







		"""simple docstring"""





		print('\n'.join(str(UpperCamelCase__	) for line in matrix	)	)







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		list:







		"""simple docstring"""





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

		A       , A       , A       , A					       = split_matrix(UpperCamelCase__	)
		A       , A       , A       , A					       = split_matrix(UpperCamelCase__	)

		A					       = actual_strassen(UpperCamelCase__ ,			matrix_subtraction(UpperCamelCase__ ,			UpperCamelCase__	)	)
		A					       = actual_strassen(matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	) ,			UpperCamelCase__	)
		A					       = actual_strassen(matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	) ,			UpperCamelCase__	)
		A					       = actual_strassen(UpperCamelCase__ ,			matrix_subtraction(UpperCamelCase__ ,			UpperCamelCase__	)	)
		A					       = actual_strassen(matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	) ,			matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	)	)
		A					       = actual_strassen(matrix_subtraction(UpperCamelCase__ ,			UpperCamelCase__	) ,			matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	)	)
		A					       = actual_strassen(matrix_subtraction(UpperCamelCase__ ,			UpperCamelCase__	) ,			matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	)	)

		A					       = matrix_addition(matrix_subtraction(matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	) ,			UpperCamelCase__	) ,			UpperCamelCase__	)
		A					       = matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	)
		A					       = matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	)
		A					       = matrix_subtraction(matrix_subtraction(matrix_addition(UpperCamelCase__ ,			UpperCamelCase__	) ,			UpperCamelCase__	) ,			UpperCamelCase__	)

		# construct the new matrix from our 4 quadrants
		A					       = []
		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  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		list:







		"""simple docstring"""





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

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

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

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









"""simple docstring"""


def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		int:







		"""simple docstring"""





		while b:
				A       , A					       = b, a % b
		return a







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		int:







		"""simple docstring"""





		return a if b == 0 else euclidean_gcd_recursive(UpperCamelCase__ ,			a % b	)







def  __snake_case       (   )      ->		List[Any]:







		"""simple docstring"""





		print(f'euclidean_gcd(3, 5) = {euclidean_gcd(3 ,			5	)}'	)
		print(f'euclidean_gcd(5, 3) = {euclidean_gcd(5 ,			3	)}'	)
		print(f'euclidean_gcd(1, 3) = {euclidean_gcd(1 ,			3	)}'	)
		print(f'euclidean_gcd(3, 6) = {euclidean_gcd(3 ,			6	)}'	)
		print(f'euclidean_gcd(6, 3) = {euclidean_gcd(6 ,			3	)}'	)

		print(f'euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3 ,			5	)}'	)
		print(f'euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5 ,			3	)}'	)
		print(f'euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1 ,			3	)}'	)
		print(f'euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3 ,			6	)}'	)
		print(f'euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6 ,			3	)}'	)


if __name__ == "__main__":
	main()





