





'''simple docstring'''




from __future__ import annotations

from typing import Generic, TypeVar

__UpperCAmelCase         =   TypeVar("""T""")




class       UpperCamelCase__			(			Generic[T]	):




     """simple docstring"""


     def __init__(		self							:	Union[str, Any]     ,		lowerCamelCase_							:	T		):

       '''simple docstring'''



       SCREAMING_SNAKE_CASE				:							List[Any]						=	data  # Assign data
       SCREAMING_SNAKE_CASE				:							Node[T] | None						=	None  # Initialize next as null
       SCREAMING_SNAKE_CASE				:							Node[T] | None						=	None  # Initialize prev as null







class       UpperCamelCase__			(			Generic[T]	):




     """simple docstring"""


     def __init__(		self							:	Optional[int]		):

       '''simple docstring'''



       SCREAMING_SNAKE_CASE				:							Node[T] | None						=	None


     def lowerCamelCase_	(		self							:	List[str]     ,		lowerCamelCase_							:	T		):

       '''simple docstring'''



       if self.head is None:
         SCREAMING_SNAKE_CASE				:							str						=	Node(lowerCamelCase_		)
       else:
         SCREAMING_SNAKE_CASE				:							Tuple						=	Node(lowerCamelCase_		)
         SCREAMING_SNAKE_CASE				:							Optional[int]						=	new_node
         SCREAMING_SNAKE_CASE				:							List[str]						=	self.head
         SCREAMING_SNAKE_CASE				:							Any						=	None
         SCREAMING_SNAKE_CASE				:							Dict						=	new_node


     def lowerCamelCase_	(		self							:	int		):

       '''simple docstring'''



       if self.head is None:
         return None
       else:
         assert self.head is not None
         SCREAMING_SNAKE_CASE				:							Tuple						=	self.head.data
         SCREAMING_SNAKE_CASE				:							str						=	self.head.next
         if self.head is not None:
           SCREAMING_SNAKE_CASE				:							str						=	None
         return temp


     def lowerCamelCase_	(		self							:	List[Any]		):

       '''simple docstring'''



       return self.head.data if self.head is not None else None


     def __len__(		self							:	Union[str, Any]		):

       '''simple docstring'''



       SCREAMING_SNAKE_CASE				:							Any						=	self.head
       SCREAMING_SNAKE_CASE				:							Dict						=	0
       while temp is not None:
         count += 1
         SCREAMING_SNAKE_CASE				:							List[Any]						=	temp.next
       return count


     def lowerCamelCase_	(		self							:	Optional[Any]		):

       '''simple docstring'''



       return self.head is None



     def lowerCamelCase_	(		self							:	str		):

       '''simple docstring'''



       print("""stack elements are:"""		)
       SCREAMING_SNAKE_CASE				:							Dict						=	self.head
       while temp is not None:
         print(temp.data     ,		end="""->"""		)
         SCREAMING_SNAKE_CASE				:							List[Any]						=	temp.next


# Code execution starts here
if __name__ == "__main__":
       # Start with the empty stack
       __UpperCAmelCase         =   Stack()

       # Insert 4 at the beginning. So stack becomes 4->None
       print("""Stack operations using Doubly LinkedList""")
       stack.push(4)

       # Insert 5 at the beginning. So stack becomes 4->5->None
       stack.push(5)

       # Insert 6 at the beginning. So stack becomes 4->5->6->None
       stack.push(6)

       # Insert 7 at the beginning. So stack becomes 4->5->6->7->None
       stack.push(7)

       # Print the stack
       stack.print_stack()

       # Print the top element
       print("""\nTop element is """, stack.top())

       # Print the stack size
       print("""Size of the stack is """, len(stack))

       # pop the top element
       stack.pop()

       # pop the top element
       stack.pop()

       # two elements have now been popped off
       stack.print_stack()

       # Print True if the stack is empty else False
       print("""\nstack is empty:""", stack.is_empty())










'''simple docstring'''




from __future__ import annotations



def 						__A						(       lowerCamelCase_	,	lowerCamelCase_	,	lowerCamelCase_	,	lowerCamelCase_					):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE,    SCREAMING_SNAKE_CASE				:							List[Any]						=	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						(       ):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE				:							Optional[Any]						=	[[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
		SCREAMING_SNAKE_CASE				:							Dict						=	int(input("""Enter the element to be searched:"""					)					)
		print(lowerCamelCase_					)
		search_in_a_sorted_matrix(lowerCamelCase_	,	len(lowerCamelCase_					)	,	len(mat[0]					)	,	lowerCamelCase_					)


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							main()



