




from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize



class 			a_					(    SCREAMING_SNAKE_CASE__    ):
	A						       =   1
	A						       =   2
	A						       =   3





	def __repr__(       self			)     ->				List[str]:




				"""simple docstring"""



				return f'{self.__class__.__name__}.{self.name}'




def lowercase						(     SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE   ) ->       float:


			'''simple docstring'''







			SCREAMING_SNAKE_CASE_	,		SCREAMING_SNAKE_CASE_			=	point
			return degrees(atana(y - miny					,						x - minx   )   )

def lowercase						(     SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE   ) ->       Direction:


			'''simple docstring'''







			SCREAMING_SNAKE_CASE_	,		SCREAMING_SNAKE_CASE_			=	starting
			SCREAMING_SNAKE_CASE_	,		SCREAMING_SNAKE_CASE_			=	via
			SCREAMING_SNAKE_CASE_	,		SCREAMING_SNAKE_CASE_			=	target
			SCREAMING_SNAKE_CASE_			=	degrees(atana(ya - ya					,						xa - xa   )   )
			via_angle %= 3_60
			SCREAMING_SNAKE_CASE_			=	degrees(atana(ya - ya					,						xa - xa   )   )
			target_angle %= 3_60
			# t-
			#  \ \
			#   \ v
			#    \|
			#     s
			# via_angle is always lower than target_angle, if direction is left.
			# If they are same, it means they are on a same line of convex hull.
			if target_angle > via_angle:
						return Direction.left
			elif target_angle == via_angle:
						return Direction.straight
			else:
						return Direction.right

def lowercase						(     SCREAMING_SNAKE_CASE   ) ->       list[tuple[int, int]]:


			'''simple docstring'''







			if len(SCREAMING_SNAKE_CASE   ) <= 2:
						# There is no convex hull
						raise ValueError('graham_scan: argument must contain more than 3 points.'   )
			if len(SCREAMING_SNAKE_CASE   ) == 3:
						return points
			# find the lowest and the most left point
			SCREAMING_SNAKE_CASE_			=	0
			SCREAMING_SNAKE_CASE_	,		SCREAMING_SNAKE_CASE_			=	maxsize, maxsize
			for i, point in enumerate(SCREAMING_SNAKE_CASE   ):
						SCREAMING_SNAKE_CASE_			=	point[0]
						SCREAMING_SNAKE_CASE_			=	point[1]
						if y < miny:
									SCREAMING_SNAKE_CASE_			=	y
									SCREAMING_SNAKE_CASE_			=	x
									SCREAMING_SNAKE_CASE_			=	i
						if y == miny and x < minx:
									SCREAMING_SNAKE_CASE_			=	x
									SCREAMING_SNAKE_CASE_			=	i

    # remove the lowest and the most left point from points for preparing for sort
			points.pop(SCREAMING_SNAKE_CASE   )

			SCREAMING_SNAKE_CASE_			=	sorted(SCREAMING_SNAKE_CASE					,						key=lambda SCREAMING_SNAKE_CASE   : angle_comparer(SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE   )   )
			# This insert actually costs complexity,
			# and you should instead add (minx, miny) into stack later.
			# I'm using insert just for easy understanding.
			sorted_points.insert(0					,						(minx, miny)   )

			SCREAMING_SNAKE_CASE_			=	deque()
			stack.append(sorted_points[0]   )
			stack.append(sorted_points[1]   )
			stack.append(sorted_points[2]   )
			# In any ways, the first 3 points line are towards left.
			# Because we sort them the angle from minx, miny.
			SCREAMING_SNAKE_CASE_			=	Direction.left

			for i in range(3					,						len(SCREAMING_SNAKE_CASE   )   ):
						while True:
									SCREAMING_SNAKE_CASE_			=	stack[-2]
									SCREAMING_SNAKE_CASE_			=	stack[-1]
									SCREAMING_SNAKE_CASE_			=	sorted_points[i]
									SCREAMING_SNAKE_CASE_			=	check_direction(SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE   )

									if next_direction == Direction.left:
												SCREAMING_SNAKE_CASE_			=	Direction.left
												break
									if next_direction == Direction.straight:
												if current_direction == Direction.left:
															# We keep current_direction as left.
															# Because if the straight line keeps as straight,
															# we want to know if this straight line is towards left.
															break
												elif current_direction == Direction.right:
															# If the straight line is towards right,
															# every previous points on those straigh line is not convex hull.
															stack.pop()
									if next_direction == Direction.right:
												stack.pop()
						stack.append(sorted_points[i]   )
			return list(SCREAMING_SNAKE_CASE   )






from __future__ import annotations

def lowercase						(     SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE					,						SCREAMING_SNAKE_CASE   ) ->       None:


			'''simple docstring'''







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


			'''simple docstring'''







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


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				main()
