






"""simple docstring"""


from __future__ import annotations

from collections.abc import Iterable






class __a   :



  def __init__(self  :		Optional[int]				,			lowercase_  :		str				,			lowercase_  :		List[Any]   )		->							Optional[Any]:
   __A	:       List[str]       =	float(lowercase_   ), float(lowercase_   )



  def __eq__(self  :		List[str]				,			lowercase_  :		int   )		->							int:
   return self.x == other.x and self.y == other.y



  def __ne__(self  :		List[Any]				,			lowercase_  :		int   )		->							Optional[int]:
   return not self == other



  def __gt__(self  :		List[Any]				,			lowercase_  :		Optional[Any]   )		->							Optional[Any]:
   if self.x > other.x:
    return True
   elif self.x == other.x:
    return self.y > other.y
   return False



  def __lt__(self  :		Union[str, Any]				,			lowercase_  :		Optional[int]   )		->							Optional[int]:
   return not self > other



  def __ge__(self  :		Tuple				,			lowercase_  :		Dict   )		->							Optional[Any]:
   if self.x > other.x:
    return True
   elif self.x == other.x:
    return self.y >= other.y
   return False



  def __le__(self  :		Dict				,			lowercase_  :		Any   )		->							Dict:
   if self.x < other.x:
    return True
   elif self.x == other.x:
    return self.y <= other.y
   return False



  def __repr__(self  :		Optional[int]   )		->							Dict:
   return f"({self.x}, {self.y})"



  def __hash__(self  :		List[str]   )		->							str:
   return hash(self.x   )






def 				a      (     UpperCamelCase_							:				list[Point] | list[list[float]] | Iterable[list[float]]     ,	)  ->		list[Point]:
 __A	:       list[Point]       =	[]
 if list_of_tuples:
  for p in list_of_tuples:
   if isinstance(UpperCamelCase_     ,	UpperCamelCase_		):
    points.append(UpperCamelCase_		)
   else:
    try:
     points.append(Point(p[0]     ,	p[1]		)		)
    except (IndexError, TypeError):
     print(
         F"Ignoring deformed point {p}. All points"
         ' must have at least 2 coordinates.'		)
 return points




def 				a      (     UpperCamelCase_							:				list[Point] | list[list[float]]		)  ->		list[Point]:

 if not hasattr(UpperCamelCase_     ,	'__iter__'		):
  __A	:       Any       =	F"Expecting an iterable object but got an non-iterable type {points}"
  raise ValueError(UpperCamelCase_		)

 if not points:
  __A	:       Dict       =	F"Expecting a list of points but got {points}"
  raise ValueError(UpperCamelCase_		)

 return _construct_points(UpperCamelCase_		)




def 				a      (     UpperCamelCase_							:				Point     ,	UpperCamelCase_							:				Point     ,	UpperCamelCase_							:				Point		)  ->		float:
 __A	:       List[Any]       =	(a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
 return det




def 				a      (     UpperCamelCase_							:				list[Point]		)  ->		list[Point]:
 __A	:       Optional[int]       =	sorted(_validate_input(UpperCamelCase_		)		)
 __A	:       Optional[int]       =	len(UpperCamelCase_		)
 __A	:       Dict       =	set()

 for i in range(n - 1		):
  for j in range(i + 1     ,	UpperCamelCase_		):
   __A	:       Union[str, Any]       =	False
   __A	:       List[str]       =	True
   for k in range(UpperCamelCase_		):
    if k != i and k != j:
     __A	:       Union[str, Any]       =	_det(points[i]     ,	points[j]     ,	points[k]		)

     if det_k > 0:
      __A	:       Any       =	True
     elif det_k < 0:
      __A	:       Any       =	True
     else:
      # point[i], point[j], point[k] all lie on a straight line
      # if point[k] is to the left of point[i] or it's to the
      # right of point[j], then point[i], point[j] cannot be
      # part of the convex hull of A
      if points[k] < points[i] or points[k] > points[j]:
       __A	:       int       =	False
       break

    if points_left_of_ij and points_right_of_ij:
     __A	:       Dict       =	False
     break

   if ij_part_of_convex_hull:
    convex_set.update([points[i], points[j]]		)

 return sorted(UpperCamelCase_		)




def 				a      (     UpperCamelCase_							:				list[Point]		)  ->		list[Point]:
 __A	:       Union[str, Any]       =	sorted(_validate_input(UpperCamelCase_		)		)
 __A	:       Dict       =	len(UpperCamelCase_		)

 # divide all the points into an upper hull and a lower hull
 # the left most point and the right most point are definitely
 # members of the convex hull by definition.
 # use these two anchors to divide all the points into two hulls,
 # an upper hull and a lower hull.

 # all points to the left (above) the line joining the extreme points belong to the
 # upper hull
 # all points to the right (below) the line joining the extreme points below to the
 # lower hull
 # ignore all points on the line joining the extreme points since they cannot be
 # part of the convex hull

 __A	:       int       =	points[0]
 __A	:       List[str]       =	points[n - 1]

 __A	:       List[Any]       =	{left_most_point, right_most_point}
 __A	:       str       =	[]
 __A	:       str       =	[]

 for i in range(1     ,	n - 1		):
  __A	:       int       =	_det(UpperCamelCase_     ,	UpperCamelCase_     ,	points[i]		)

  if det > 0:
   upper_hull.append(points[i]		)
  elif det < 0:
   lower_hull.append(points[i]		)

 _construct_hull(UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_		)
 _construct_hull(UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_		)

 return sorted(UpperCamelCase_		)




def 				a      (     UpperCamelCase_							:				list[Point]     ,	UpperCamelCase_							:				Point     ,	UpperCamelCase_							:				Point     ,	UpperCamelCase_							:				set[Point]		)  ->		None:
 if points:
  __A	:       str       =	None
  __A	:       str       =	float('-inf'		)
  __A	:       str       =	[]

  for p in points:
   __A	:       List[str]       =	_det(UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_		)

   if det > 0:
    candidate_points.append(UpperCamelCase_		)

    if det > extreme_point_distance:
     __A	:       int       =	det
     __A	:       Tuple       =	p

  if extreme_point:
   _construct_hull(UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_		)
   convex_set.add(UpperCamelCase_		)
   _construct_hull(UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_     ,	UpperCamelCase_		)




def 				a      (     UpperCamelCase_							:				list[Point]		)  ->		list[Point]:
 __A	:       Optional[int]       =	sorted(_validate_input(UpperCamelCase_		)		)
 __A	:       Any       =	len(UpperCamelCase_		)

 __A	:       Optional[int]       =	points[:2]
 for i in range(2     ,	UpperCamelCase_		):
  __A	:       Tuple       =	_det(convex_hull[1]     ,	convex_hull[0]     ,	points[i]		)
  if det > 0:
   convex_hull.insert(0     ,	points[i]		)
   break
  elif det < 0:
   convex_hull.append(points[i]		)
   break
  else:
   __A	:       Optional[Any]       =	points[i]
 i += 1

 for j in range(UpperCamelCase_     ,	UpperCamelCase_		):
  if (
      _det(convex_hull[0]     ,	convex_hull[-1]     ,	points[j]		) > 0
      and _det(convex_hull[-1]     ,	convex_hull[0]     ,	points[1]		) < 0
  ):
   # The point lies within the convex hull
   continue

  convex_hull.insert(0     ,	points[j]		)
  convex_hull.append(points[j]		)
  while _det(convex_hull[0]     ,	convex_hull[1]     ,	convex_hull[2]		) >= 0:
   del convex_hull[1]
  while _det(convex_hull[-1]     ,	convex_hull[-2]     ,	convex_hull[-3]		) <= 0:
   del convex_hull[-2]

    # `convex_hull` is contains the convex hull in circular order
 return sorted(convex_hull[1:] if len(UpperCamelCase_		) > 3 else convex_hull		)




def 				a      (     )  ->		Any:
 __A	:       int       =	[
     (0, 3),
     (2, 2),
     (1, 1),
     (2, 1),
     (3, 0),
     (0, 0),
     (3, 3),
     (2, -1),
     (2, -4),
     (1, -3),
 ]
 # the convex set of points is
 # [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
 __A	:       Dict       =	convex_hull_bf(UpperCamelCase_		)

 __A	:       Dict       =	convex_hull_recursive(UpperCamelCase_		)
 assert results_bf == results_recursive

 __A	:       int       =	convex_hull_melkman(UpperCamelCase_		)
 assert results_bf == results_melkman

 print(UpperCamelCase_		)


if __name__ == "__main__":
   main()













"""simple docstring"""


from string import ascii_uppercase




def 				a (     UpperCamelCase_							:				str     ,	UpperCamelCase_							:				str     ,	UpperCamelCase_							:				bool = False     ,	UpperCamelCase_							:				str = ascii_uppercase		)  ->		str:
 __A	:       List[str]       =	keyword.upper()
 __A	:       str       =	plaintext.upper()
 __A	:       int       =	set(UpperCamelCase_		)

 # create a list of unique characters in the keyword - their order matters
 # it determines how we will map plaintext characters to the ciphertext
 __A	:       int       =	[]
 for char in keyword:
  if char in alphabet_set and char not in unique_chars:
   unique_chars.append(UpperCamelCase_		)
    # the number of those unique characters will determine the number of rows
 __A	:       Any       =	len(UpperCamelCase_		)

 # create a shifted version of the alphabet
 __A	:       str       =	unique_chars + [
     char for char in alphabet if char not in unique_chars
 ]

 # create a modified alphabet by splitting the shifted alphabet into rows
 __A	:       int       =	[
     shifted_alphabet[k : k + num_unique_chars_in_keyword]
     for k in range(0     ,	2_6     ,	UpperCamelCase_		)
 ]

 # map the alphabet characters to the modified alphabet characters
 # going 'vertically' through the modified alphabet - consider columns first
 __A	:       Any       =	{}
 __A	:       Union[str, Any]       =	0
 for column in range(UpperCamelCase_		):
  for row in modified_alphabet:
   # if current row (the last one) is too short, break out of loop
   if len(UpperCamelCase_		) <= column:
    break

   # map current letter to letter in modified alphabet
   __A	:       str       =	row[column]
   letter_index += 1

 if verbose:
  print(UpperCamelCase_		)
 # create the encrypted text by mapping the plaintext to the modified alphabet
 return "".join(mapping[char] if char in mapping else char for char in plaintext		)


if __name__ == "__main__":
   # example use
   print(mixed_keyword("""college""", """UNIVERSITY"""))





