from __future__ import annotations




def   _UpperCamelCase   (			snake_case__,    snake_case__,    snake_case__							)						->   tuple[float, float]:
							assert (
							    c % greatest_common_divisor(lowerCamelCase__,    lowerCamelCase__							) == 0
							)  # greatest_common_divisor(a,b) function implemented below
							((__UpperCAmelCase)    ,	(__UpperCAmelCase)    ,	(__UpperCAmelCase))						:			Optional[int]         =   extended_gcd(lowerCamelCase__,    lowerCamelCase__							)  # extended_gcd(a,b) function implemented below
							__UpperCAmelCase						:			Optional[int]         =   c / d
							return (r * x, r * y)




def   _UpperCamelCase   (			snake_case__,    snake_case__,    snake_case__,    snake_case__ = 2							)						->   None:
							((__UpperCAmelCase)    ,	(__UpperCAmelCase))						:			str         =   diophantine(lowerCamelCase__,    lowerCamelCase__,    lowerCamelCase__							)  # Initial value
							__UpperCAmelCase						:			int         =   greatest_common_divisor(lowerCamelCase__,    lowerCamelCase__							)
							__UpperCAmelCase						:			int         =   a // d
							__UpperCAmelCase						:			Tuple         =   b // d

							for i in range(lowerCamelCase__							):
														__UpperCAmelCase						:			Optional[int]         =   xa + i * q
														__UpperCAmelCase						:			Dict         =   ya - i * p
														print(lowerCamelCase__,    lowerCamelCase__							)




def   _UpperCamelCase   (			snake_case__,    snake_case__							)						->   int:




							if a < b:
														__UpperCAmelCase    ,	__UpperCAmelCase						:			Union[str, Any]         =   b, a

							while a % b != 0:
														__UpperCAmelCase    ,	__UpperCAmelCase						:			Optional[int]         =   b, a % b

							return b




def   _UpperCamelCase   (			snake_case__,    snake_case__							)						->   tuple[int, int, int]:
							assert a >= 0 and b >= 0

							if b == 0:
														__UpperCAmelCase    ,	__UpperCAmelCase    ,	__UpperCAmelCase						:			Any         =   a, 1, 0
							else:
														((__UpperCAmelCase)    ,	(__UpperCAmelCase)    ,	(__UpperCAmelCase))						:			Union[str, Any]         =   extended_gcd(lowerCamelCase__,    a % b							)
														__UpperCAmelCase						:			Union[str, Any]         =   q
														__UpperCAmelCase						:			str         =   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)





import unittest
from dataclasses import dataclass
from typing import Optional

from transformers.utils import ModelOutput




@dataclass
class 					_snake_case						(						_lowercase				):
					lowerCamelCase__:		float
					lowerCamelCase__:		Optional[float]  =     None
					lowerCamelCase__:		Optional[float]  =     None




class 					_snake_case						(						unittest.TestCase				):
					def    _lowerCamelCase (  self:				Union[str, Any]     )    ->				List[Any]:
												__UpperCAmelCase						:			str         =   ModelOutputTest(a=30     )
												self.assertEqual(x.a	,  30     )
												self.assertIsNone(x.b     )
												self.assertIsNone(x.c     )
												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			List[Any]         =   x.d
					def    _lowerCamelCase (  self:				Optional[int]     )    ->				str:
												__UpperCAmelCase						:			Union[str, Any]         =   ModelOutputTest(a=30	,  b=10     )
												self.assertEqual(x[0]	,  30     )
												self.assertEqual(x[1]	,  10     )
												self.assertEqual(x[:2]	,  (30, 10)     )
												self.assertEqual(x[:]	,  (30, 10)     )

												__UpperCAmelCase						:			Optional[Any]         =   ModelOutputTest(a=30	,  c=10     )
												self.assertEqual(x[0]	,  30     )
												self.assertEqual(x[1]	,  10     )
												self.assertEqual(x[:2]	,  (30, 10)     )
												self.assertEqual(x[:]	,  (30, 10)     )
					def    _lowerCamelCase (  self:				Tuple     )    ->				List[str]:
												__UpperCAmelCase						:			str         =   ModelOutputTest(a=30	,  b=10     )
												self.assertEqual(x["a"]	,  30     )
												self.assertEqual(x["b"]	,  10     )
												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			Dict         =   x["c"]

												__UpperCAmelCase						:			Tuple         =   ModelOutputTest(a=30	,  c=10     )
												self.assertEqual(x["a"]	,  30     )
												self.assertEqual(x["c"]	,  10     )
												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			Optional[Any]         =   x["b"]
					def    _lowerCamelCase (  self:				str     )    ->				Any:
												__UpperCAmelCase						:			Union[str, Any]         =   ModelOutputTest(a=30     )
												self.assertEqual(list(x.keys()     )	,  ["a"]     )
												self.assertEqual(list(x.values()     )	,  [30]     )
												self.assertEqual(list(x.items()     )	,  [("a", 30)]     )
												self.assertEqual(list(__lowerCamelCase     )	,  ["a"]     )

												__UpperCAmelCase						:			str         =   ModelOutputTest(a=30	,  b=10     )
												self.assertEqual(list(x.keys()     )	,  ["a", "b"]     )
												self.assertEqual(list(x.values()     )	,  [30, 10]     )
												self.assertEqual(list(x.items()     )	,  [("a", 30), ("b", 10)]     )
												self.assertEqual(list(__lowerCamelCase     )	,  ["a", "b"]     )

												__UpperCAmelCase						:			Any         =   ModelOutputTest(a=30	,  c=10     )
												self.assertEqual(list(x.keys()     )	,  ["a", "c"]     )
												self.assertEqual(list(x.values()     )	,  [30, 10]     )
												self.assertEqual(list(x.items()     )	,  [("a", 30), ("c", 10)]     )
												self.assertEqual(list(__lowerCamelCase     )	,  ["a", "c"]     )

												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			Dict         =   x.update({"d": 20}     )
												with self.assertRaises(__lowerCamelCase     ):
																			del x["a"]
												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			List[Any]         =   x.pop("a"     )
												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			str         =   x.setdefault("d"	,  32     )
					def    _lowerCamelCase (  self:				List[str]     )    ->				str:
												__UpperCAmelCase						:			Optional[Any]         =   ModelOutputTest(a=30     )
												__UpperCAmelCase						:			Tuple         =   10
												self.assertEqual(x.a	,  10     )
												self.assertEqual(x["a"]	,  10     )
					def    _lowerCamelCase (  self:				Optional[int]     )    ->				Dict:
												__UpperCAmelCase						:			str         =   ModelOutputTest(a=30     )
												__UpperCAmelCase						:			Optional[int]         =   10
												self.assertEqual(x.a	,  10     )
												self.assertEqual(x["a"]	,  10     )
					def    _lowerCamelCase (  self:				List[Any]     )    ->				Optional[int]:
												__UpperCAmelCase						:			Tuple         =   ModelOutputTest({"a": 30, "b": 10}     )
												self.assertEqual(list(x.keys()     )	,  ["a", "b"]     )
												self.assertEqual(x.a	,  30     )
												self.assertEqual(x.b	,  10     )





					def    _lowerCamelCase (  self:				Optional[int]     )    ->				Union[str, Any]:
												__UpperCAmelCase						:			Dict         =   ModelOutputTest([("a", 30), ("b", 10)]     )
												self.assertEqual(list(x.keys()     )	,  ["a", "b"]     )
												self.assertEqual(x.a	,  30     )
												self.assertEqual(x.b	,  10     )

												with self.assertRaises(__lowerCamelCase     ):
																			__UpperCAmelCase						:			Any         =   ModelOutputTest([("a", 30), (10, 10)]     )

												__UpperCAmelCase						:			Dict         =   ModelOutputTest(a=(30, 30)     )
												self.assertEqual(list(x.keys()     )	,  ["a"]     )
												self.assertEqual(x.a	,  (30, 30)     )




