
"""simple docstring"""







from __future__ import annotations

import math
import random
from typing import Any







class 							__magic_name__     :





					def __init__(				self   :							Any    ):
												__snake_case     			=       []
												__snake_case     			=       0
												__snake_case     			=       0





					def 							lowerCAmelCase      (				self   :							List[str]    ):
												return self.head == self.tail





					def 							lowerCAmelCase      (				self   :							Any							,						snake_case_   :							Any    ):
												self.data.append(snake_case_    )
												__snake_case     			=       self.tail + 1





					def 							lowerCAmelCase      (				self   :							Optional[int]    ):
												__snake_case     			=       self.data[self.head]
												__snake_case     			=       self.head + 1
												return ret





					def 							lowerCAmelCase      (				self   :							List[Any]    ):
												return self.tail - self.head





					def 							lowerCAmelCase      (				self   :							Optional[Any]    ):
												print(self.data    )
												print("**************"    )
												print(self.data[self.head : self.tail]    )







class 							__magic_name__     :





					def __init__(				self   :							Optional[int]							,						snake_case_   :							Any    ):
												__snake_case     			=       data
												__snake_case     			=       None
												__snake_case     			=       None
												__snake_case     			=       1





					def 							lowerCAmelCase      (				self   :							Optional[Any]    ):
												return self.data





					def 							lowerCAmelCase      (				self   :							Any    ):
												return self.left





					def 							lowerCAmelCase      (				self   :							List[str]    ):
												return self.right





					def 							lowerCAmelCase      (				self   :							str    ):
												return self.height





					def 							lowerCAmelCase      (				self   :							Any							,						snake_case_   :							Any    ):
												__snake_case     			=       data





					def 							lowerCAmelCase      (				self   :							List[str]							,						snake_case_   :							MyNode | None    ):
												__snake_case     			=       node





					def 							lowerCAmelCase      (				self   :							Optional[Any]							,						snake_case_   :							MyNode | None    ):
												__snake_case     			=       node





					def 							lowerCAmelCase      (				self   :							int							,						snake_case_   :							int    ):
												__snake_case     			=       height




def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     int:







							"""simple docstring"""


							if node is None:
														return 0
							return node.get_height()
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     int:







							"""simple docstring"""


							if a > b:
														return a
							return b
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     MyNode:







							"""simple docstring"""


							print("left rotation node:"							,    node.get_data() )
							__snake_case     			=       node.get_left()
							assert ret is not None
							node.set_left(ret.get_right() )
							ret.set_right(SCREAMING_SNAKE_CASE )
							__snake_case     			=       my_max(get_height(node.get_right() )							,    get_height(node.get_left() ) ) + 1
							node.set_height(SCREAMING_SNAKE_CASE )
							__snake_case     			=       my_max(get_height(ret.get_right() )							,    get_height(ret.get_left() ) ) + 1
							ret.set_height(SCREAMING_SNAKE_CASE )
							return ret
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     MyNode:







							"""simple docstring"""


							print("right rotation node:"							,    node.get_data() )
							__snake_case     			=       node.get_right()
							assert ret is not None
							node.set_right(ret.get_left() )
							ret.set_left(SCREAMING_SNAKE_CASE )
							__snake_case     			=       my_max(get_height(node.get_right() )							,    get_height(node.get_left() ) ) + 1
							node.set_height(SCREAMING_SNAKE_CASE )
							__snake_case     			=       my_max(get_height(ret.get_right() )							,    get_height(ret.get_left() ) ) + 1
							ret.set_height(SCREAMING_SNAKE_CASE )
							return ret
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     MyNode:







							"""simple docstring"""


							__snake_case     			=       node.get_left()
							assert left_child is not None
							node.set_left(left_rotation(SCREAMING_SNAKE_CASE ) )
							return right_rotation(SCREAMING_SNAKE_CASE )
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     MyNode:







							"""simple docstring"""


							__snake_case     			=       node.get_right()
							assert right_child is not None
							node.set_right(right_rotation(SCREAMING_SNAKE_CASE ) )
							return left_rotation(SCREAMING_SNAKE_CASE )
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     MyNode | None:







							"""simple docstring"""


							if node is None:
														return MyNode(SCREAMING_SNAKE_CASE )
							if data < node.get_data():
														node.set_left(insert_node(node.get_left()							,    SCREAMING_SNAKE_CASE ) )
														if (
														    get_height(node.get_left() ) - get_height(node.get_right() ) == 2
														):  # an unbalance detected
																					__snake_case     			=       node.get_left()
																					assert left_child is not None
																					if (
																					    data < left_child.get_data()
																					):  # new node is the left child of the left child
																												__snake_case     			=       right_rotation(SCREAMING_SNAKE_CASE )
																					else:
																												__snake_case     			=       lr_rotation(SCREAMING_SNAKE_CASE )
							else:
														node.set_right(insert_node(node.get_right()							,    SCREAMING_SNAKE_CASE ) )
														if get_height(node.get_right() ) - get_height(node.get_left() ) == 2:
																					__snake_case     			=       node.get_right()
																					assert right_child is not None
																					if data < right_child.get_data():
																												__snake_case     			=       rl_rotation(SCREAMING_SNAKE_CASE )
																					else:
																												__snake_case     			=       left_rotation(SCREAMING_SNAKE_CASE )
							__snake_case     			=       my_max(get_height(node.get_right() )							,    get_height(node.get_left() ) ) + 1
							node.set_height(SCREAMING_SNAKE_CASE )
							return node
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     Any:







							"""simple docstring"""


							while True:
														__snake_case     			=       root.get_right()
														if right_child is None:
																					break
														__snake_case     			=       right_child
							return root.get_data()
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     Any:







							"""simple docstring"""


							while True:
														__snake_case     			=       root.get_left()
														if left_child is None:
																					break
														__snake_case     			=       left_child
							return root.get_data()
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     MyNode | None:







							"""simple docstring"""


							__snake_case     			=       root.get_left()
							__snake_case     			=       root.get_right()
							if root.get_data() == data:
														if left_child is not None and right_child is not None:
																					__snake_case     			=       get_left_most(SCREAMING_SNAKE_CASE )
																					root.set_data(SCREAMING_SNAKE_CASE )
																					root.set_right(del_node(SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE ) )
														elif left_child is not None:
																					__snake_case     			=       left_child
														elif right_child is not None:
																					__snake_case     			=       right_child
														else:
																					return None
							elif root.get_data() > data:
														if left_child is None:
																					print("No such data" )
																					return root
														else:
																					root.set_left(del_node(SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE ) )
							else:  # root.get_data() < data
														if right_child is None:
																					return root
														else:
																					root.set_right(del_node(SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE ) )

							if get_height(SCREAMING_SNAKE_CASE ) - get_height(SCREAMING_SNAKE_CASE ) == 2:
														assert right_child is not None
														if get_height(right_child.get_right() ) > get_height(right_child.get_left() ):
																					__snake_case     			=       left_rotation(SCREAMING_SNAKE_CASE )
														else:
																					__snake_case     			=       rl_rotation(SCREAMING_SNAKE_CASE )
							elif get_height(SCREAMING_SNAKE_CASE ) - get_height(SCREAMING_SNAKE_CASE ) == -2:
														assert left_child is not None
														if get_height(left_child.get_left() ) > get_height(left_child.get_right() ):
																					__snake_case     			=       right_rotation(SCREAMING_SNAKE_CASE )
														else:
																					__snake_case     			=       lr_rotation(SCREAMING_SNAKE_CASE )
							__snake_case     			=       my_max(get_height(root.get_right() )							,    get_height(root.get_left() ) ) + 1
							root.set_height(SCREAMING_SNAKE_CASE )
							return root







class 							__magic_name__     :





					def __init__(				self   :							int    ):
												__snake_case     			=       None





					def 							lowerCAmelCase      (				self   :							Any    ):
												return get_height(self.root    )





					def 							lowerCAmelCase      (				self   :							Union[str, Any]							,						snake_case_   :							Any    ):
												print("insert:" + str(snake_case_    )    )
												__snake_case     			=       insert_node(self.root							,						snake_case_    )





					def 							lowerCAmelCase      (				self   :							List[Any]							,						snake_case_   :							Any    ):
												print("delete:" + str(snake_case_    )    )
												if self.root is None:
																			print("Tree is empty!"    )
																			return
												__snake_case     			=       del_node(self.root							,						snake_case_    )





					def __str__(				self   :							Tuple							,						):  # a level traversale, gives a more intuitive look on the tree
												__snake_case     			=       ""
												__snake_case     			=       MyQueue()
												q.push(self.root    )
												__snake_case     			=       self.get_height()
												if layer == 0:
																			return output
												__snake_case     			=       0
												while not q.is_empty():
																			__snake_case     			=       q.pop()
																			__snake_case     			=       " " * int(math.pow(2							,						layer - 1    )    )
																			output += space
																			if node is None:
																										output += "*"
																										q.push(snake_case_    )
																										q.push(snake_case_    )
																			else:
																										output += str(node.get_data()    )
																										q.push(node.get_left()    )
																										q.push(node.get_right()    )
																			output += space
																			__snake_case     			=       cnt + 1
																			for i in range(100    ):
																										if cnt == math.pow(2							,						snake_case_    ) - 1:
																																	__snake_case     			=       layer - 1
																																	if layer == 0:
																																								output += "\n*************************************"
																																								return output
																																	output += "\n"
																																	break
												output += "\n*************************************"
												return output




def   __UpperCamelCase   (					)  ->     None:







							"""simple docstring"""


							import doctest

							doctest.testmod()


if __name__ == "__main__":
		_test()
		_SCREAMING_SNAKE_CASE	       =      AVLtree()
		_SCREAMING_SNAKE_CASE	       =      list(range(10))
		random.shuffle(lst)
		for i in lst:
				t.insert(i)
				print(str(t))
		random.shuffle(lst)
		for i in lst:
				t.del_node(i)
				print(str(t))


"""simple docstring"""







from heapq import heappop, heappush

import numpy as np
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    )  ->     tuple[float | int, list[tuple[int, int]]]:







							"""simple docstring"""


							__snake_case			,   __snake_case     			=       grid.shape
							__snake_case     			=       [-1, 1, 0, 0]
							__snake_case     			=       [0, 0, -1, 1]
							if allow_diagonal:
														dx += [-1, -1, 1, 1]
														dy += [-1, 1, -1, 1]

							__snake_case			,   __snake_case     			=       [(0, source)], set()
							__snake_case     			=       np.full((rows, cols)							,    np.inf )
							__snake_case     			=       0
							__snake_case     			=       np.empty((rows, cols)							,    dtype=SCREAMING_SNAKE_CASE )
							__snake_case     			=       None

							while queue:
														((__snake_case)			,   (__snake_case))     			=       heappop(SCREAMING_SNAKE_CASE )
														if (x, y) in visited:
																					continue
														visited.add((x, y) )

														if (x, y) == destination:
																					__snake_case     			=       []
																					while (x, y) != source:
																												path.append((x, y) )
																												__snake_case			,   __snake_case     			=       predecessors[x, y]
																					path.append(SCREAMING_SNAKE_CASE )  # add the source manually
																					path.reverse()
																					return matrix[destination], path

														for i in range(len(SCREAMING_SNAKE_CASE ) ):
																					__snake_case			,   __snake_case     			=       x + dx[i], y + dy[i]
																					if 0 <= nx < rows and 0 <= ny < cols:
																												__snake_case     			=       grid[nx][ny]
																												if next_node == 1 and matrix[nx, ny] > dist + 1:
																																			heappush(SCREAMING_SNAKE_CASE							,    (dist + 1, (nx, ny)) )
																																			__snake_case     			=       dist + 1
																																			__snake_case     			=       (x, y)

							return np.inf, []


if __name__ == "__main__":
		import doctest

		doctest.testmod()
