




"""simple docstring"""

from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize
class     A__      (      lowercase_     ):
	A_							:				Tuple						     =      1
	A_							:				Union[str, Any]						     =      2
	A_							:				Union[str, Any]						     =      3




	def __repr__(   self  :	Dict	)					-> Union[str, Any]:
						return f'''{self.__class__.__name__}.{self.name}'''




def       snake_case__	(       lowerCAmelCase   :		tuple[int, int]				,					lowerCAmelCase   :		int				,					lowerCAmelCase   :		int		):
					__snake_case      ,      __snake_case          =	point
					return degrees(atana(y - miny				,					x - minx		)		)




def       snake_case__	(       lowerCAmelCase   :		tuple[int, int]				,					lowerCAmelCase   :		tuple[int, int]				,					lowerCAmelCase   :		tuple[int, int]		):
					__snake_case      ,      __snake_case          =	starting
					__snake_case      ,      __snake_case          =	via
					__snake_case      ,      __snake_case          =	target
					__snake_case          =	degrees(atana(ya - ya				,					xa - xa		)		)
					via_angle %= 360
					__snake_case          =	degrees(atana(ya - ya				,					xa - xa		)		)
					target_angle %= 360
					# 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       snake_case__	(       lowerCAmelCase   :		list[tuple[int, int]]		):

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

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

					__snake_case          =	sorted(lowerCAmelCase				,					key=lambda lowerCAmelCase		: angle_comparer(lowerCAmelCase				,					lowerCAmelCase				,					lowerCAmelCase		)		)
					# 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)		)

					__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.
					__snake_case          =	Direction.left

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

															if next_direction == Direction.left:
																				__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(lowerCAmelCase		)








"""simple docstring"""

from functools import lru_cache




@lru_cache
def       snake_case__	(       lowerCAmelCase   :		int		):
					if not isinstance(lowerCAmelCase				,					lowerCAmelCase		):
										raise TypeError("""k must be an integer."""		)
					if k < 0:
										raise ValueError("""k integer must be greater or equal to zero."""		)
					if k == 0:
										return 0
					elif k == 1:
										return 1
					else:
										return fibonacci(k - 1		) + fibonacci(k - 2		)




def       snake_case__	(       lowerCAmelCase   :		list				,					lowerCAmelCase   :		int		):
					__snake_case          =	len(lowerCAmelCase		)
					# Find m such that F_m >= n where F_i is the i_th fibonacci number.
					__snake_case          =	0
					while True:
										if fibonacci(lowerCAmelCase		) >= len_list:
															__snake_case          =	i
															break
										i += 1
					__snake_case          =	0
					while fibb_k > 0:
										__snake_case          =	min(
										    offset + fibonacci(fibb_k - 1		)				,					len_list - 1		)  # Prevent out of range
										__snake_case          =	arr[index_k]
										if item_k_1 == val:
															return index_k
										elif val < item_k_1:
															fibb_k -= 1
										elif val > item_k_1:
															offset += fibonacci(fibb_k - 1		)
															fibb_k -= 2
					else:
										return -1


if __name__ == "__main__":
		import doctest

		doctest.testmod()


