




def        __UpperCAmelCase						(							lowerCamelCase_ :     list  )       ->  list:







			"""simple docstring"""





			if len(lowerCamelCase_  ) <= 1:
						return [tuple(lowerCamelCase_  )]

			SCREAMING_SNAKE_CASE_   : Optional[int]					  =      []

			def generate(lowerCamelCase_ :     int  ,							lowerCamelCase_ :     list  ):
						SCREAMING_SNAKE_CASE_   : Any					  =      [0] * n
						res.append(tuple(lowerCamelCase_  )  )

						SCREAMING_SNAKE_CASE_   : Dict					  =      0
						while i < n:
									if c[i] < i:
												if i % 2 == 0:
															SCREAMING_SNAKE_CASE_  ,    SCREAMING_SNAKE_CASE_   : List[str]					  =      arr[i], arr[0]
												else:
															SCREAMING_SNAKE_CASE_  ,    SCREAMING_SNAKE_CASE_   : List[Any]					  =      arr[i], arr[c[i]]
												res.append(tuple(lowerCamelCase_  )  )
												c[i] += 1
												SCREAMING_SNAKE_CASE_   : int					  =      0
									else:
												SCREAMING_SNAKE_CASE_   : str					  =      0
												i += 1

			generate(len(lowerCamelCase_  )  ,							lowerCamelCase_  )
			return res


if __name__ == "__main__":
						UpperCamelCase__ :   Any						=							input('''Enter numbers separated by a comma:\n''').strip()
						UpperCamelCase__ :   List[Any]						=							[int(item) for item in user_input.split(''',''')]
						print(heaps(arr))










"""simple docstring"""






from __future__ import annotations






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			tuple[int, int]:



			'''simple docstring'''
			if b == 0:
						return (1, 0)
			((a__) ,	(a__))  :	List[Any]		 =			extended_euclid(lowerCAmelCase__							,			a % b			)
			a__  :	str		 =			a // b
			return (y, x - k * y)






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			((a__) ,	(a__))  :	Tuple		 =			extended_euclid(lowerCAmelCase__							,			lowerCAmelCase__			)
			a__  :	List[str]		 =			na * na
			a__  :	Union[str, Any]		 =			ra * x * na + ra * y * na
			return (n % m + m) % m






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			((a__) ,	(a__))  :	Optional[Any]		 =			extended_euclid(lowerCAmelCase__							,			lowerCAmelCase__			)
			if b < 0:
						a__  :	Optional[int]		 =			(b % n + n) % n
			return b






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			a__ ,	a__  :	List[Any]		 =			invert_modulo(lowerCAmelCase__							,			lowerCAmelCase__			), invert_modulo(lowerCAmelCase__							,			lowerCAmelCase__			)
			a__  :	Dict		 =			na * na
			a__  :	Any		 =			ra * x * na + ra * y * na
			return (n % m + m) % m


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

		testmod(name='''chinese_remainder_theorem''', verbose=True)
		testmod(name='''chinese_remainder_theorem2''', verbose=True)
		testmod(name='''invert_modulo''', verbose=True)
		testmod(name='''extended_euclid''', verbose=True)