



'''simple docstring'''




from __future__ import annotations


def     lowerCAmelCase_       (     _lowerCamelCase:       int	,				_lowerCamelCase:       int	,				_lowerCamelCase:       int ):
		assert n > 1 and a > 0 and greatest_common_divisor(_lowerCamelCase	,				_lowerCamelCase ) == 1
		((__SCREAMING_SNAKE_CASE)	,						(__SCREAMING_SNAKE_CASE)	,						(__SCREAMING_SNAKE_CASE))	:		int   	=		extended_gcd(_lowerCamelCase	,				_lowerCamelCase )  # Implemented below
		__SCREAMING_SNAKE_CASE	:		Tuple   	=		(b * s) % n
		return x


def     lowerCAmelCase_       (     _lowerCamelCase:       int	,				_lowerCamelCase:       int ):
		((__SCREAMING_SNAKE_CASE)	,						(__SCREAMING_SNAKE_CASE))	:		int   	=		extended_euclid(_lowerCamelCase	,				_lowerCamelCase )  # Implemented below
		if b < 0:
				__SCREAMING_SNAKE_CASE	:		Any   	=		(b % n + n) % n
		return b


def     lowerCAmelCase_       (     _lowerCamelCase:       int	,				_lowerCamelCase:       int	,				_lowerCamelCase:       int ):
		__SCREAMING_SNAKE_CASE	:		Tuple   	=		invert_modulo(_lowerCamelCase	,				_lowerCamelCase )
		__SCREAMING_SNAKE_CASE	:		Optional[Any]   	=		(b * s) % n
		return x


def     lowerCAmelCase_       (     _lowerCamelCase:       int	,				_lowerCamelCase:       int ):
		assert a >= 0 and b >= 0

		if b == 0:
				__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		Optional[Any]   	=		a, 1, 0
		else:
				((__SCREAMING_SNAKE_CASE)	,						(__SCREAMING_SNAKE_CASE)	,						(__SCREAMING_SNAKE_CASE))	:		str   	=		extended_gcd(_lowerCamelCase	,				a % b )
				__SCREAMING_SNAKE_CASE	:		Dict   	=		q
				__SCREAMING_SNAKE_CASE	:		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)


def     lowerCAmelCase_       (     _lowerCamelCase:       int	,				_lowerCamelCase:       int ):
		if b == 0:
				return (1, 0)
		((__SCREAMING_SNAKE_CASE)	,						(__SCREAMING_SNAKE_CASE))	:		str   	=		extended_euclid(_lowerCamelCase	,				a % b )
		__SCREAMING_SNAKE_CASE	:		Optional[int]   	=		a // b
		return (y, x - k * y)


def     lowerCAmelCase_       (     _lowerCamelCase:       int	,				_lowerCamelCase:       int ):
		if a < b:
				__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		List[Any]   	=		b, a

		while a % b != 0:
				__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		List[Any]   	=		b, a % b

		return b


if __name__ == "__main__":
						from doctest import testmod

						testmod(name='''modular_division''', verbose=True)
						testmod(name='''modular_division2''', verbose=True)
						testmod(name='''invert_modulo''', verbose=True)
						testmod(name='''extended_gcd''', verbose=True)
						testmod(name='''extended_euclid''', verbose=True)
						testmod(name='''greatest_common_divisor''', verbose=True)




'''simple docstring'''




from __future__ import annotations

import random
from collections.abc import Iterable
from typing import Any, Generic, TypeVar

UpperCamelCase__	:     str    =			TypeVar('''T''', bound=bool)






class 						_UpperCamelCase  (							Generic[T]   ):


			'''simple docstring'''

			def __init__(							self					:			str							,					lowerCAmelCase__					:			T						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		T   	=		value
					__SCREAMING_SNAKE_CASE	:		RandomizedHeapNode[T] | None   	=		None
					__SCREAMING_SNAKE_CASE	:		RandomizedHeapNode[T] | None   	=		None

			@property
			def UpperCamelCase__ (							self					:			Any						):





					"""simple docstring"""






					return self._value



			@staticmethod
			def UpperCamelCase__ (							lowerCAmelCase__					:			RandomizedHeapNode[T] | None							,					lowerCAmelCase__					:			RandomizedHeapNode[T] | None						):





					"""simple docstring"""






					if not roota:
							return roota

					if not roota:
							return roota

					if roota.value > roota.value:
							__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		List[str]   	=		roota, roota

					if random.choice([True, False]						):
							__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		Tuple   	=		roota.right, roota.left

					__SCREAMING_SNAKE_CASE	:		Tuple   	=		RandomizedHeapNode.merge(roota.left							,					lowerCAmelCase__						)

					return roota






class 						_UpperCamelCase  (							Generic[T]   ):


			'''simple docstring'''

			def __init__(							self					:			Optional[int]							,					lowerCAmelCase__					:			Iterable[T] | None = ()						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		RandomizedHeapNode[T] | None   	=		None

					if data:
							for item in data:
									self.insert(lowerCAmelCase__						)

			def UpperCamelCase__ (							self					:			Dict							,					lowerCAmelCase__					:			T						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		Dict   	=		RandomizedHeapNode.merge(self._root							,					RandomizedHeapNode(lowerCAmelCase__						)						)

			def UpperCamelCase__ (							self					:			Union[str, Any]						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		Tuple   	=		self.top()

					if self._root is None:
							return None

					__SCREAMING_SNAKE_CASE	:		Union[str, Any]   	=		RandomizedHeapNode.merge(self._root.left							,					self._root.right						)

					return result

			def UpperCamelCase__ (							self					:			Union[str, Any]						):





					"""simple docstring"""






					if not self._root:
							raise IndexError("""Can't get top element for the empty heap."""						)
					return self._root.value

			def UpperCamelCase__ (							self					:			List[Any]						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		List[str]   	=		None

			def UpperCamelCase__ (							self					:			Optional[Any]						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		int   	=		[]
					while self:
							result.append(self.pop()						)

					return result



			def __bool__(							self					:			List[Any]						):





					"""simple docstring"""






					return self._root is not None


if __name__ == "__main__":
						import doctest

						doctest.testmod()