
from __future__ import annotations
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     int  ):


					'''simple docstring'''

					assert (
					    c % greatest_common_divisor(__magic_name__							,  __magic_name__  ) == 0
					)  # greatest_common_divisor(a,b) function implemented below
					((lowerCAmelCase)	,							(lowerCAmelCase)	,							(lowerCAmelCase))		:					Optional[int]  	=     extended_gcd(__magic_name__							,  __magic_name__  )  # extended_gcd(a,b) function implemented below
					lowerCAmelCase		:					Optional[int]  	=     c / d
					return (r * x, r * y)
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     int = 2  ):


					'''simple docstring'''

					((lowerCAmelCase)	,							(lowerCAmelCase))		:					Optional[int]  	=     diophantine(__magic_name__							,  __magic_name__							,  __magic_name__  )  # Initial value
					lowerCAmelCase		:					Union[str, Any]  	=     greatest_common_divisor(__magic_name__							,  __magic_name__  )
					lowerCAmelCase		:					List[Any]  	=     a // d
					lowerCAmelCase		:					List[Any]  	=     b // d

					for i in range(__magic_name__  ):
										lowerCAmelCase		:					int  	=     xa + i * q
										lowerCAmelCase		:					Tuple  	=     ya - i * p
										print(__magic_name__							,  __magic_name__  )
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     int  ):


					'''simple docstring'''

					if a < b:
										lowerCAmelCase	,							lowerCAmelCase		:					str  	=     b, a

					while a % b != 0:
										lowerCAmelCase	,							lowerCAmelCase		:					List[str]  	=     b, a % b

					return b
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     int  ):


					'''simple docstring'''

					assert a >= 0 and b >= 0

					if b == 0:
										lowerCAmelCase	,							lowerCAmelCase	,							lowerCAmelCase		:					Optional[Any]  	=     a, 1, 0
					else:
										((lowerCAmelCase)	,							(lowerCAmelCase)	,							(lowerCAmelCase))		:					str  	=     extended_gcd(__magic_name__							,  a % b  )
										lowerCAmelCase		:					Any  	=     q
										lowerCAmelCase		:					Union[str, Any]  	=     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 ..utils import requires_backends


__SCREAMING_SNAKE_CASE			:   Union[str, Any]         =     None


class 		__magic_name__   :





		def __init__(							self    :	Optional[int]						,  *lowerCamelCase__    :	List[str]						,  **lowerCamelCase__    :	Optional[Any]				):
							requires_backends(self						,  ['''detectron2''']				)





		@classmethod
		def       _A							(							cls    :	Dict						,  *lowerCamelCase__    :	List[str]						,  **lowerCamelCase__    :	Optional[Any]				):
							requires_backends(cls						,  ['''detectron2''']				)
