
'''simple docstring'''





from __future__ import annotations

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


class 	UpperCamelCase__					(      SCREAMING_SNAKE_CASE):
 UpperCAmelCase__      :      Union[str, Any]  			=   1
 UpperCAmelCase__      :      Any  			=   2
 UpperCAmelCase__      :      str  			=   3






 def __repr__(     self					:Any     )			->     Any:







       '''simple docstring'''



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





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase		)->     float:







      """simple docstring"""
      __A		, __A    		=     point
      return degrees(atana(y - miny ,					x - minx		)		)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase		)->     Direction:







      """simple docstring"""
      __A		, __A    		=     starting
      __A		, __A    		=     via
      __A		, __A    		=     target
      __A    		=     degrees(atana(ya - ya ,					xa - xa		)		)
      via_angle %= 3_6_0
      __A    		=     degrees(atana(ya - ya ,					xa - xa		)		)
      target_angle %= 3_6_0
      # 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							(						UpperCAmelCase		)->     list[tuple[int, int]]:







      """simple docstring"""

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

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

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

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

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

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








'''simple docstring'''





from __future__ import annotations





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase		)->     tuple[float, float]:







      """simple docstring"""
      assert (
          c % greatest_common_divisor(UpperCAmelCase ,					UpperCAmelCase		) == 0
      )  # greatest_common_divisor(a,b) function implemented below
      ((__A)		, (__A)		, (__A))    		=     extended_gcd(UpperCAmelCase ,					UpperCAmelCase		)  # extended_gcd(a,b) function implemented below
      __A    		=     c / d
      return (r * x, r * y)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase = 2		)->     None:







      """simple docstring"""
      ((__A)		, (__A))    		=     diophantine(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase		)  # Initial value
      __A    		=     greatest_common_divisor(UpperCAmelCase ,					UpperCAmelCase		)
      __A    		=     a // d
      __A    		=     b // d

      for i in range(UpperCAmelCase		):
            __A    		=     xa + i * q
            __A    		=     ya - i * p
            print(UpperCAmelCase ,					UpperCAmelCase		)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase		)->     int:







      """simple docstring"""
      if a < b:
            __A		, __A    		=     b, a

      while a % b != 0:
            __A		, __A    		=     b, a % b

      return b





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase		)->     tuple[int, int, int]:







      """simple docstring"""
      assert a >= 0 and b >= 0

      if b == 0:
            __A		, __A		, __A    		=     a, 1, 0
      else:
            ((__A)		, (__A)		, (__A))    		=     extended_gcd(UpperCAmelCase ,					a % b		)
            __A    		=     q
            __A    		=     p - q * (a // b)

      assert a % d == 0 and b % d == 0
      assert d == a * x + b * y

      return (d, x, y)


if __name__ == "__main__":
 from doctest import testmod

 testmod(name="diophantine", verbose=True)
 testmod(name="diophantine_all_soln", verbose=True)
 testmod(name="extended_gcd", verbose=True)
 testmod(name="greatest_common_divisor", verbose=True)






