



'''simple docstring'''



from __future__ import annotations

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Any






@dataclass
class 					UpperCAmelCase__	:
					a      :     int
					a      :     Node | None        =							None
					a      :     Node | None        =							None



def   __lowerCAmelCase					(							):






	'''simple docstring'''




	__lowerCAmelCase												=  Node(1					)
	__lowerCAmelCase												=  Node(2					)
	__lowerCAmelCase												=  Node(3					)
	__lowerCAmelCase												=  Node(4					)
	__lowerCAmelCase												=  Node(5					)
	return tree



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None					):






	'''simple docstring'''




	return [root.data, *preorder(root.left					), *preorder(root.right					)] if root else []



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None					):






	'''simple docstring'''




	return postorder(root.left					) + postorder(root.right					) + [root.data] if root else []



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None					):






	'''simple docstring'''




	return [*inorder(root.left					), root.data, *inorder(root.right					)] if root else []



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None					):






	'''simple docstring'''




	return (max(height(root.left					)				,		height(root.right					)					) + 1) if root else 0



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None					):






	'''simple docstring'''




	__lowerCAmelCase												=  []

	if root is None:
		return output

	__lowerCAmelCase												=  deque([root]					)

	while process_queue:
		__lowerCAmelCase												=  process_queue.popleft()
		output.append(node.data					)

		if node.left:
			process_queue.append(node.left					)
		if node.right:
			process_queue.append(node.right					)
	return output



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None				,		lowerCamelCase   :						int					):






	'''simple docstring'''




	__lowerCAmelCase												=  []

	def populate_output(lowerCamelCase   :						Node | None				,		lowerCamelCase   :						int					) -> None:
		if not root:
			return
		if level == 1:
			output.append(root.data					)
		elif level > 1:
			populate_output(root.left				,		level - 1					)
			populate_output(root.right				,		level - 1					)

	populate_output(lowerCamelCase				,		lowerCamelCase					)
	return output



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None				,		lowerCamelCase   :						int					):






	'''simple docstring'''




	__lowerCAmelCase												=  []

	def populate_output(lowerCamelCase   :						Node | None				,		lowerCamelCase   :						int					) -> None:
		if root is None:
			return
		if level == 1:
			output.append(root.data					)
		elif level > 1:
			populate_output(root.right				,		level - 1					)
			populate_output(root.left				,		level - 1					)

	populate_output(lowerCamelCase				,		lowerCamelCase					)
	return output



def   __lowerCAmelCase					(							lowerCamelCase   :						Node | None					):






	'''simple docstring'''




	if root is None:
		return []

	__lowerCAmelCase												=  []

	__lowerCAmelCase												=  0
	__lowerCAmelCase												=  height(lowerCamelCase					)

	for h in range(1				,		height_tree + 1					):
		if not flag:
			output.append(get_nodes_from_left_to_right(lowerCamelCase				,		lowerCamelCase					)					)
			__lowerCAmelCase												=  1
		else:
			output.append(get_nodes_from_right_to_left(lowerCamelCase				,		lowerCamelCase					)					)
			__lowerCAmelCase												=  0

	return output



def   __lowerCAmelCase					(							):  # Main function for testing.






	'''simple docstring'''




	__lowerCAmelCase												=  make_tree()
	print(f'''In-order Traversal: {inorder(lowerCamelCase					)}'''					)
	print(f'''Pre-order Traversal: {preorder(lowerCamelCase					)}'''					)
	print(f'''Post-order Traversal: {postorder(lowerCamelCase					)}'''				,		"\n"					)

	print(f'''Height of Tree: {height(lowerCamelCase					)}'''				,		"\n"					)

	print("Complete Level Order Traversal: "					)
	print(level_order(lowerCamelCase					)				,		"\n"					)

	print("Level-wise order Traversal: "					)

	for level in range(1				,		height(lowerCamelCase					) + 1					):
		print(f'''Level {level}:'''				,		get_nodes_from_left_to_right(lowerCamelCase				,		level=lowerCamelCase					)					)

	print("\nZigZag order Traversal: "					)
	print(zigzag(lowerCamelCase					)					)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()




'''simple docstring'''



from __future__ import annotations

import math



def   __lowerCAmelCase					(							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"					)
	__lowerCAmelCase												=  [
	    [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   __lowerCAmelCase					(							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   __lowerCAmelCase					(							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   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




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

	__lowerCAmelCase												=  len(lowerCamelCase					)
	__lowerCAmelCase												=  matrix_length // 2

	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase				,		lowerCamelCase					)] for i in range(lowerCamelCase					)]
	__lowerCAmelCase												=  [
	    [a[i][j] for j in range(lowerCamelCase				,		lowerCamelCase					)] for i in range(lowerCamelCase				,		lowerCamelCase					)
	]

	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase					)] for i in range(lowerCamelCase					)]
	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase					)] for i in range(lowerCamelCase				,		lowerCamelCase					)]

	return top_left, top_right, bot_left, bot_right



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




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



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




	print("\n".join(str(lowerCamelCase					) for line in matrix					)					)



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




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

	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  split_matrix(lowerCamelCase					)
	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  split_matrix(lowerCamelCase					)

	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)

	__lowerCAmelCase												=  matrix_addition(matrix_subtraction(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_addition(lowerCamelCase				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_addition(lowerCamelCase				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_subtraction(matrix_subtraction(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)				,		lowerCamelCase					)

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






	'''simple docstring'''




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

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

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

	__lowerCAmelCase												=  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__":
	lowerCAmelCase	:		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],
	]
	lowerCAmelCase	:		Any				=   [[0, 2, 1, 1], [1_6, 2, 3, 3], [2, 2, 7, 7], [1_3, 1_1, 2_2, 4]]
	print(strassen(matrixa, matrixa))