
'''simple docstring'''

from typing import Any







def 	A  (   UpperCamelCase_       :  list    ,						UpperCamelCase_       :  list    ,						UpperCamelCase_       :  dict    ,						UpperCamelCase_       :  dict    ,						UpperCamelCase_       :  dict    ,						)       ->							list:







			'''simple docstring'''



			_validation(
			    UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						)
			# Creates data structures and fill initial step
			lowerCAmelCase__										=				{}
			lowerCAmelCase__										=				{}
			for state in states_space:
						lowerCAmelCase__										=				observations_space[0]
						lowerCAmelCase__										=				(
						    initial_probabilities[state] * emission_probabilities[state][observation]
						)
						lowerCAmelCase__										=				None

			# Fills the data structure with the probabilities of
			# different transitions and pointers to previous states
			for o in range(1    ,						len(UpperCamelCase_   )   ):
						lowerCAmelCase__										=				observations_space[o]
						lowerCAmelCase__										=				observations_space[o - 1]
						for state in states_space:
									# Calculates the argmax for probability function
									lowerCAmelCase__										=				""
									lowerCAmelCase__										=				-1
									for k_state in states_space:
												lowerCAmelCase__										=				(
												    probabilities[(k_state, prior_observation)]
												    * transition_probabilities[k_state][state]
												    * emission_probabilities[state][observation]
												)
												if probability > max_probability:
															lowerCAmelCase__										=				probability
															lowerCAmelCase__										=				k_state

            # Update probabilities and pointers dicts
									lowerCAmelCase__										=				(
									    probabilities[(arg_max, prior_observation)]
									    * transition_probabilities[arg_max][state]
									    * emission_probabilities[state][observation]
									)

									lowerCAmelCase__										=				arg_max

    # The final observation
			lowerCAmelCase__										=				observations_space[len(UpperCamelCase_   ) - 1]

			# argmax for given final observation
			lowerCAmelCase__										=				""
			lowerCAmelCase__										=				-1
			for k_state in states_space:
						lowerCAmelCase__										=				probabilities[(k_state, final_observation)]
						if probability > max_probability:
									lowerCAmelCase__										=				probability
									lowerCAmelCase__										=				k_state
			lowerCAmelCase__										=				arg_max

			# Process pointers backwards
			lowerCAmelCase__										=				last_state
			lowerCAmelCase__										=				[]
			for o in range(len(UpperCamelCase_   ) - 1    ,						-1    ,						-1   ):
						result.append(UpperCamelCase_   )
						lowerCAmelCase__										=				pointers[previous, observations_space[o]]
			result.reverse()

			return result







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						)       ->							None:







			'''simple docstring'''



			_validate_not_empty(
			    UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						)
			_validate_lists(UpperCamelCase_    ,						UpperCamelCase_   )
			_validate_dicts(
			    UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_   )







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						)       ->							None:







			'''simple docstring'''



			if not all(
			    [
			        observations_space,
			        states_space,
			        initial_probabilities,
			        transition_probabilities,
			        emission_probabilities,
			    ]   ):
						raise ValueError("There's an empty parameter"   )







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any   )       ->							None:







			'''simple docstring'''



			_validate_list(UpperCamelCase_    ,						"observations_space"   )
			_validate_list(UpperCamelCase_    ,						"states_space"   )







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  str   )       ->							None:







			'''simple docstring'''



			if not isinstance(_object    ,						UpperCamelCase_   ):
						lowerCAmelCase__										=				F"""{var_name} must be a list"""
						raise ValueError(UpperCamelCase_   )
			else:
						for x in _object:
									if not isinstance(UpperCamelCase_    ,						UpperCamelCase_   ):
												lowerCAmelCase__										=				F"""{var_name} must be a list of strings"""
												raise ValueError(UpperCamelCase_   )







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  Any    ,						)       ->							None:







			'''simple docstring'''



			_validate_dict(UpperCamelCase_    ,						"initial_probabilities"    ,						UpperCamelCase_   )
			_validate_nested_dict(UpperCamelCase_    ,						"transition_probabilities"   )
			_validate_nested_dict(UpperCamelCase_    ,						"emission_probabilities"   )







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  str   )       ->							None:







			'''simple docstring'''



			_validate_dict(_object    ,						UpperCamelCase_    ,						UpperCamelCase_   )
			for x in _object.values():
						_validate_dict(UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_    ,						UpperCamelCase_   )







def 	A  (   UpperCamelCase_       :  Any    ,						UpperCamelCase_       :  str    ,						UpperCamelCase_       :  type    ,						UpperCamelCase_       :  bool = False   )       ->							None:







			'''simple docstring'''



			if not isinstance(_object    ,						UpperCamelCase_   ):
						lowerCAmelCase__										=				F"""{var_name} must be a dict"""
						raise ValueError(UpperCamelCase_   )
			if not all(isinstance(UpperCamelCase_    ,						UpperCamelCase_   ) for x in _object   ):
						lowerCAmelCase__										=				F"""{var_name} all keys must be strings"""
						raise ValueError(UpperCamelCase_   )
			if not all(isinstance(UpperCamelCase_    ,						UpperCamelCase_   ) for x in _object.values()   ):
						lowerCAmelCase__										=				"nested dictionary " if nested else ""
						lowerCAmelCase__										=				F"""{var_name} {nested_text}all values must be {value_type.__name__}"""
						raise ValueError(UpperCamelCase_   )


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

		testmod()






"""simple docstring"""


def      lowerCamelCase_					(   __lowerCAmelCase							)				->   list:




						'''simple docstring'''



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

						lowerCamelCase__   =[]

						def generate(__lowerCAmelCase  ,       __lowerCAmelCase							):
												lowerCamelCase__   =[0] * n
												res.append(tuple(__lowerCAmelCase							)							)

												lowerCamelCase__   =0
												while i < n:
																		if c[i] < i:
																								if i % 2 == 0:
																														lowerCamelCase__   , lowerCamelCase__   =arr[i], arr[0]
																								else:
																														lowerCamelCase__   , lowerCamelCase__   =arr[i], arr[c[i]]
																								res.append(tuple(__lowerCAmelCase							)							)
																								c[i] += 1
																								lowerCamelCase__   =0
																		else:
																								lowerCamelCase__   =0
																								i += 1

						generate(len(__lowerCAmelCase							)  ,       __lowerCAmelCase							)
						return res


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


