





from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


_SCREAMING_SNAKE_CASE   						=		{
    """configuration_prophetnet""": ["""PROPHETNET_PRETRAINED_CONFIG_ARCHIVE_MAP""", """ProphetNetConfig"""],
    """tokenization_prophetnet""": ["""ProphetNetTokenizer"""],
}

try:
						if not is_torch_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						_SCREAMING_SNAKE_CASE   						=		[
						    """PROPHETNET_PRETRAINED_MODEL_ARCHIVE_LIST""",
						    """ProphetNetDecoder""",
						    """ProphetNetEncoder""",
						    """ProphetNetForCausalLM""",
						    """ProphetNetForConditionalGeneration""",
						    """ProphetNetModel""",
						    """ProphetNetPreTrainedModel""",
						]


if TYPE_CHECKING:
						from .configuration_prophetnet import PROPHETNET_PRETRAINED_CONFIG_ARCHIVE_MAP, ProphetNetConfig
						from .tokenization_prophetnet import ProphetNetTokenizer

						try:
												if not is_torch_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .modeling_prophetnet import (
												    PROPHETNET_PRETRAINED_MODEL_ARCHIVE_LIST,
												    ProphetNetDecoder,
												    ProphetNetEncoder,
												    ProphetNetForCausalLM,
												    ProphetNetForConditionalGeneration,
												    ProphetNetModel,
												    ProphetNetPreTrainedModel,
												)

else:
						import sys

						_SCREAMING_SNAKE_CASE   						=		_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)






from __future__ import annotations





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






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





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase = 2				):
					"""simple docstring"""






					((lowercase)   ,      (lowercase))						   =       diophantine(_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)  # Initial value
					lowercase						   =       greatest_common_divisor(_UpperCAmelCase       ,			_UpperCAmelCase				)
					lowercase						   =       a // d
					lowercase						   =       b // d

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





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if a < b:
										lowercase   ,      lowercase						   =       b, a

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

					return b





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					assert a >= 0 and b >= 0

					if b == 0:
										lowercase   ,      lowercase   ,      lowercase						   =       a, 1, 0
					else:
										((lowercase)   ,      (lowercase)   ,      (lowercase))						   =       extended_gcd(_UpperCAmelCase       ,			a % b				)
										lowercase						   =       q
										lowercase						   =       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)






