





from __future__ import annotations

def     UpperCAmelCase_						(						_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int							)  ->							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     UpperCAmelCase_						(						_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int = 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     UpperCAmelCase_						(						_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int							)  ->							int:
     '''simple docstring'''


     if a < b:
          A_      ,						A_					      =					b, a

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

     return b

def     UpperCAmelCase_						(						_UpperCAmelCase       :int     ,	_UpperCAmelCase       :int							)  ->							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)










from __future__ import annotations

def     UpperCAmelCase_						(						_UpperCAmelCase       :list							)  ->							int | float:
     '''simple docstring'''


     A_					      =					sorted(_UpperCAmelCase							)
     A_					      =					len(_UpperCAmelCase							)
     A_					      =					length >> 1
     return (
         (sorted_list[mid_index] + sorted_list[mid_index - 1]) / 2
         if length % 2 == 0
         else sorted_list[mid_index]
     )

def     UpperCAmelCase_						(						)  ->							Optional[Any]:
     '''simple docstring'''


     import doctest

     doctest.testmod()


if __name__ == "__main__":
      main()



