






from __future__ import annotations



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

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



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__ = 2	):


		'''simple docstring'''

		((__A) ,   (__A))    =							diophantine(lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__	)  # Initial value
		__A    =							greatest_common_divisor(lowerCAmelCase__					,     lowerCAmelCase__	)
		__A    =							a // d
		__A    =							b // d

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



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

		if a < b:
				__A ,   __A    =							b, a

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

		return b



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

		assert a >= 0 and b >= 0

		if b == 0:
				__A ,   __A ,   __A    =							a, 1, 0
		else:
				((__A) ,   (__A) ,   (__A))    =							extended_gcd(lowerCAmelCase__					,     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)


'''simple docstring'''
from __future__ import annotations

import math
import random







def 				__UpperCamelCase (					__UpperCAmelCase  :					int ,   __UpperCAmelCase  :					int ,   __UpperCAmelCase  :					int			)							->	list[int]:
  lowercase				:							Union[str, Any]									=   d * e - 1
  lowercase				:							List[str]									=   0
  lowercase				:							Tuple									=   0
  while p == 0:
    lowercase				:							Optional[Any]									=   random.randint(2 ,   n - 1			)
    lowercase				:							Dict									=   k
    while True:
      if t % 2 == 0:
        lowercase				:							List[Any]									=   t // 2
        lowercase				:							Union[str, Any]									=   (g**t) % n
        lowercase				:							Optional[Any]									=   math.gcd(x - 1 ,   __UpperCAmelCase			)
        if x > 1 and y > 1:
          lowercase				:							Dict									=   y
          lowercase				:							Any									=   n // y
          break  # find the correct factors
      else:
        break  # t is not divisible by 2, break and choose another g
  return sorted([p, q]			)


if __name__ == "__main__":
 import doctest

 doctest.testmod()