from typing import Any




def       lowerCAmelCase_     (		lowercase:							list  ,					lowercase:							list  ,					lowercase:							dict  ,					lowercase:							dict  ,					lowercase:							dict  ,					)    ->				list:







 '''simple docstring'''
 _validation(
     UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					)
 # Creates data structures and fill initial step
 _UpperCamelCase:     int							= {}
 _UpperCamelCase:     Optional[Any]							= {}
 for state in states_space:
  _UpperCamelCase:     Dict							= observations_space[0]
  _UpperCamelCase:     str							= (
      initial_probabilities[state] * emission_probabilities[state][observation]
  )
  _UpperCamelCase:     Optional[int]							= None

 # Fills the data structure with the probabilities of
 # different transitions and pointers to previous states
 for o in range(1  ,					len(UpperCAmelCase__		)		):
  _UpperCamelCase:     Dict							= observations_space[o]
  _UpperCamelCase:     List[Any]							= observations_space[o - 1]
  for state in states_space:
   # Calculates the argmax for probability function
   _UpperCamelCase:     List[str]							= ''''''
   _UpperCamelCase:     Optional[Any]							= -1
   for k_state in states_space:
    _UpperCamelCase:     Union[str, Any]							= (
        probabilities[(k_state, prior_observation)]
        * transition_probabilities[k_state][state]
        * emission_probabilities[state][observation]
    )
    if probability > max_probability:
     _UpperCamelCase:     Union[str, Any]							= probability
     _UpperCamelCase:     Union[str, Any]							= k_state

            # Update probabilities and pointers dicts
   _UpperCamelCase:     Optional[Any]							= (
       probabilities[(arg_max, prior_observation)]
       * transition_probabilities[arg_max][state]
       * emission_probabilities[state][observation]
   )

   _UpperCamelCase:     Optional[Any]							= arg_max

    # The final observation
 _UpperCamelCase:     List[Any]							= observations_space[len(UpperCAmelCase__		) - 1]

 # argmax for given final observation
 _UpperCamelCase:     Tuple							= ''''''
 _UpperCamelCase:     Any							= -1
 for k_state in states_space:
  _UpperCamelCase:     List[Any]							= probabilities[(k_state, final_observation)]
  if probability > max_probability:
   _UpperCamelCase:     Optional[Any]							= probability
   _UpperCamelCase:     Any							= k_state
 _UpperCamelCase:     Tuple							= arg_max

 # Process pointers backwards
 _UpperCamelCase:     List[str]							= last_state
 _UpperCamelCase:     Any							= []
 for o in range(len(UpperCAmelCase__		) - 1  ,					-1  ,					-1		):
  result.append(UpperCAmelCase__		)
  _UpperCamelCase:     Tuple							= pointers[previous, observations_space[o]]
 result.reverse()

 return result




def       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							Any  ,					)    ->				None:







 '''simple docstring'''
 _validate_not_empty(
     UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					)
 _validate_lists(UpperCAmelCase__  ,					UpperCAmelCase__		)
 _validate_dicts(
     UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__		)




def       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							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       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							Any		)    ->				None:







 '''simple docstring'''
 _validate_list(UpperCAmelCase__  ,					'''observations_space'''		)
 _validate_list(UpperCAmelCase__  ,					'''states_space'''		)




def       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							str		)    ->				None:







 '''simple docstring'''
 if not isinstance(_object  ,					UpperCAmelCase__		):
  _UpperCamelCase:     Union[str, Any]							= F"""{var_name} must be a list"""
  raise ValueError(UpperCAmelCase__		)
 else:
  for x in _object:
   if not isinstance(UpperCAmelCase__  ,					UpperCAmelCase__		):
    _UpperCamelCase:     Optional[Any]							= F"""{var_name} must be a list of strings"""
    raise ValueError(UpperCAmelCase__		)




def       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							Any  ,					lowercase:							Any  ,					)    ->				None:







 '''simple docstring'''
 _validate_dict(UpperCAmelCase__  ,					'''initial_probabilities'''  ,					UpperCAmelCase__		)
 _validate_nested_dict(UpperCAmelCase__  ,					'''transition_probabilities'''		)
 _validate_nested_dict(UpperCAmelCase__  ,					'''emission_probabilities'''		)




def       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							str		)    ->				None:







 '''simple docstring'''
 _validate_dict(_object  ,					UpperCAmelCase__  ,					UpperCAmelCase__		)
 for x in _object.values():
  _validate_dict(UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__  ,					UpperCAmelCase__		)




def       lowerCAmelCase_     (		lowercase:							Any  ,					lowercase:							str  ,					lowercase:							type  ,					lowercase:							bool = False		)    ->				None:







 '''simple docstring'''
 if not isinstance(_object  ,					UpperCAmelCase__		):
  _UpperCamelCase:     Any							= F"""{var_name} must be a dict"""
  raise ValueError(UpperCAmelCase__		)
 if not all(isinstance(UpperCAmelCase__  ,					UpperCAmelCase__		) for x in _object		):
  _UpperCamelCase:     Tuple							= F"""{var_name} all keys must be strings"""
  raise ValueError(UpperCAmelCase__		)
 if not all(isinstance(UpperCAmelCase__  ,					UpperCAmelCase__		) for x in _object.values()		):
  _UpperCamelCase:     int							= '''nested dictionary ''' if nested else ''''''
  _UpperCamelCase:     Any							= F"""{var_name} {nested_text}all values must be {value_type.__name__}"""
  raise ValueError(UpperCAmelCase__		)


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

  testmod()
def       lowerCAmelCase_     (		lowercase:							int = 10**9		)    ->				int:







 '''simple docstring'''
 _UpperCamelCase:     List[Any]							= 1
 _UpperCamelCase:     Dict							= 2

 _UpperCamelCase:     Tuple							= 0
 _UpperCamelCase:     int							= 0
 _UpperCamelCase:     Dict							= 0
 while perimeter <= max_perimeter:
  perimeters_sum += perimeter

  prev_value += 2 * value
  value += prev_value

  _UpperCamelCase:     str							= 2 * value + 2 if i % 2 == 0 else 2 * value - 2
  i += 1

 return perimeters_sum


if __name__ == "__main__":
  print(f"""{solution() = }""")