





'''simple docstring'''




def 			_lowerCAmelCase     (    __snake_case    :					Optional[Any] = 1_00     )	->	Dict:
     __A		:					Union[str, Any]						=			(n * (n + 1) // 2) ** 2
     __A		:					Optional[Any]						=			n * (n + 1) * (2 * n + 1) // 6
     return sum_cubes - sum_squares


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

from typing import Any


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		):
      _validation(
          UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		)
      # Creates data structures and fill initial step
      UpperCamelCase__     : dict											=					{}
      UpperCamelCase__     : dict											=					{}
      for state in states_space:
            UpperCamelCase__     : Optional[int]											=					observations_space[0]
            UpperCamelCase__     : Any											=					(
                initial_probabilities[state] * emission_probabilities[state][observation]
            )
            UpperCamelCase__     : Union[str, Any]											=					None

      # Fills the data structure with the probabilities of
      # different transitions and pointers to previous states
      for o in range(1			,		len(UpperCamelCase__		)		):
            UpperCamelCase__     : str											=					observations_space[o]
            UpperCamelCase__     : Union[str, Any]											=					observations_space[o - 1]
            for state in states_space:
                  # Calculates the argmax for probability function
                  UpperCamelCase__     : int											=					''''''
                  UpperCamelCase__     : List[str]											=					-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__     : Tuple											=					probability
                              UpperCamelCase__     : Union[str, Any]											=					k_state

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

                  UpperCamelCase__     : Optional[Any]											=					arg_max

    # The final observation
      UpperCamelCase__     : List[str]											=					observations_space[len(UpperCamelCase__		) - 1]

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

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

      return result


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		):
      _validate_not_empty(
          UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		)
      _validate_lists(UpperCamelCase__			,		UpperCamelCase__		)
      _validate_dicts(
          UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__		)


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


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__		):
      _validate_list(UpperCamelCase__			,		'''observations_space'''		)
      _validate_list(UpperCamelCase__			,		'''states_space'''		)


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__		):
      if not isinstance(_object			,		UpperCamelCase__		):
            UpperCamelCase__     : List[Any]											=					f'''{var_name} must be a list'''
            raise ValueError(UpperCamelCase__		)
      else:
            for x in _object:
                  if not isinstance(UpperCamelCase__			,		UpperCamelCase__		):
                        UpperCamelCase__     : List[Any]											=					f'''{var_name} must be a list of strings'''
                        raise ValueError(UpperCamelCase__		)


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		):
      _validate_dict(UpperCamelCase__			,		'''initial_probabilities'''			,		UpperCamelCase__		)
      _validate_nested_dict(UpperCamelCase__			,		'''transition_probabilities'''		)
      _validate_nested_dict(UpperCamelCase__			,		'''emission_probabilities'''		)


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__		):
      _validate_dict(_object			,		UpperCamelCase__			,		UpperCamelCase__		)
      for x in _object.values():
            _validate_dict(UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__		)


def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__			,		UpperCamelCase__ = False		):
      if not isinstance(_object			,		UpperCamelCase__		):
            UpperCamelCase__     : List[str]											=					f'''{var_name} must be a dict'''
            raise ValueError(UpperCamelCase__		)
      if not all(isinstance(UpperCamelCase__			,		UpperCamelCase__		) for x in _object		):
            UpperCamelCase__     : Dict											=					f'''{var_name} all keys must be strings'''
            raise ValueError(UpperCamelCase__		)
      if not all(isinstance(UpperCamelCase__			,		UpperCamelCase__		) for x in _object.values()		):
            UpperCamelCase__     : Optional[Any]											=					'''nested dictionary ''' if nested else ''''''
            UpperCamelCase__     : Optional[Any]											=					f'''{var_name} {nested_text}all values must be {value_type.__name__}'''
            raise ValueError(UpperCamelCase__		)


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

    testmod()


