



from __future__ import annotations


def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase      ,					_UpperCamelCase      ,					_UpperCamelCase			):
				_UpperCAmelCase					, _UpperCAmelCase						:  str     					=	m - 1, 0
				while i >= 0 and j < n:
								if key == mat[i][j]:
												print(F'''Key {key} found at row- {i + 1} column- {j + 1}'''			)
												return
								if key < mat[i][j]:
												i -= 1
								else:
												j += 1
				print(F'''Key {key} not found'''			)


def 	_A	(   ):
				_UpperCAmelCase						:  List[Any]     					=	[[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
				_UpperCAmelCase						:  Any     					=	int(input('''Enter the element to be searched:'''			)			)
				print(_UpperCamelCase			)
				search_in_a_sorted_matrix(_UpperCamelCase      ,					len(_UpperCamelCase			)      ,					len(mat[0]			)      ,					_UpperCamelCase			)


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					main()





class 							lowerCAmelCase_		:







		def __init__(    self  :   int       ,		UpperCAmelCase_  :   int					)       ->		None:


						'''simple docstring'''







						_UpperCAmelCase						:  Tuple     					=	data
						_UpperCAmelCase						:  BinaryTreeNode | None     					=	None
						_UpperCAmelCase						:  BinaryTreeNode | None     					=	None


def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase			):
				if node is None:
								_UpperCAmelCase						:  Union[str, Any]     					=	BinaryTreeNode(_UpperCamelCase			)
								return node

				# binary search tree is not empty,
				# so we will insert it into the tree
				# if new_value is less than value of data in node,
				#  add it to left subtree and proceed recursively
				if new_value < node.data:
								_UpperCAmelCase						:  Any     					=	insert(node.left_child      ,					_UpperCamelCase			)
				else:
								# if new_value is greater than value of data in node,
								#  add it to right subtree and proceed recursively
								_UpperCAmelCase						:  List[Any]     					=	insert(node.right_child      ,					_UpperCamelCase			)
				return node


def 	_A	(   _UpperCamelCase			):  # if node is None,return
				if node:
								_UpperCAmelCase						:  str     					=	inorder(node.left_child			)
								_UpperCAmelCase						:  Union[str, Any]     					=	[*inorder_array, node.data]
								_UpperCAmelCase						:  Optional[int]     					=	inorder_array + inorder(node.right_child			)
				else:
								_UpperCAmelCase						:  Tuple     					=	[]
				return inorder_array


def 	_A	(   ):
				_UpperCAmelCase						:  Dict     					=	insert(_UpperCamelCase      ,					15			)
				insert(_UpperCamelCase      ,					10			)
				insert(_UpperCamelCase      ,					25			)
				insert(_UpperCamelCase      ,					6			)
				insert(_UpperCamelCase      ,					14			)
				insert(_UpperCamelCase      ,					20			)
				insert(_UpperCamelCase      ,					60			)
				return root


def 	_A	(   ):
				# main function
				_UpperCAmelCase						:  Tuple     					=	make_tree()
				print('''Printing values of binary search tree in Inorder Traversal.'''			)
				inorder(_UpperCamelCase			)


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					main()
