





'''simple docstring'''


from __future__ import annotations




def    __a (     UpperCAmelCase       ,			UpperCAmelCase       ,			UpperCAmelCase       ,			UpperCAmelCase    )      ->None:



	"""simple docstring"""







	A  ,    A							  =      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 (     )      ->None:



	"""simple docstring"""







	A							  =      [[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
	A							  =      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()








'''simple docstring'''


from __future__ import annotations



class 							__UpperCAmelCase  :







		'''simple docstring'''







		def __init__(self						:      Any      ,      _lowerCAmelCase						:      int      ):
			A							  =      value
			A							  =      None
			A							  =      None






class 							__UpperCAmelCase  :







		'''simple docstring'''







		__lowerCAmelCase 				=    42







		def __init__(self						:      List[str]      ):
			A							  =      0







		def        A     (self						:      Dict      ,      _lowerCAmelCase						:      Node | None      ,      _lowerCAmelCase						:      int      ):
			if node is None:
				return

			if path_sum == self.target:
				self.paths += 1

			if node.left:
				self.depth_first_search(node.left      ,      path_sum + node.left.value      )
			if node.right:
				self.depth_first_search(node.right      ,      path_sum + node.right.value      )







		def        A     (self						:      Optional[Any]      ,      _lowerCAmelCase						:      Node | None      ,      _lowerCAmelCase						:      int | None = None      ):
			if node is None:
				return 0
			if target is not None:
				A							  =      target

			self.depth_first_search(_lowerCAmelCase      ,      node.value      )
			self.path_sum(node.left      )
			self.path_sum(node.right      )

			return self.paths


if __name__ == "__main__":
				import doctest

				doctest.testmod()

