

'''simple docstring'''





from abc import ABC, abstractmethod
from typing import List, Optional





class 		__SCREAMING_SNAKE_CASE							(			lowercase__      ):







				def __init__(       self     :		str   ):
										'''simple docstring'''
										# test for the above condition
										self.test()







				def  lowerCamelCase_	(       self     :		Tuple   ):
										'''simple docstring'''
										lowercase :							int    		=0
										lowercase :							List[Any]    		=False
										while not completed:
																if counter == 1:
																						self.reset()
																lowercase :							Dict    		=self.advance()
																if not self.does_advance(UpperCAmelCase__   ):
																						raise Exception(
																						    '''Custom Constraint is not defined correctly. self.does_advance(self.advance()) must be true.'''   )

																lowercase		,	lowercase		,	lowercase :							str    		=self.update(UpperCAmelCase__   )
																counter += 1

																if counter > 10000:
																						raise Exception('''update() does not fulfill the constraint.'''   )

										if self.remaining() != 0:
																raise Exception('''Custom Constraint is not defined correctly.'''   )







				@abstractmethod
				def  lowerCamelCase_	(       self     :		Any   ):
										'''simple docstring'''
										raise NotImplementedError(
										    F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''   )







				@abstractmethod
				def  lowerCamelCase_	(       self     :		List[str]		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										raise NotImplementedError(
										    F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''   )







				@abstractmethod
				def  lowerCamelCase_	(       self     :		Union[str, Any]		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										raise NotImplementedError(
										    F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''   )







				@abstractmethod
				def  lowerCamelCase_	(       self     :		Optional[int]   ):
										'''simple docstring'''
										raise NotImplementedError(
										    F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''   )







				@abstractmethod
				def  lowerCamelCase_	(       self     :		List[str]   ):
										'''simple docstring'''
										raise NotImplementedError(
										    F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''   )







				@abstractmethod
				def  lowerCamelCase_	(       self     :		Optional[int]		,					UpperCAmelCase__     :		Optional[Any]=False   ):
										'''simple docstring'''
										raise NotImplementedError(
										    F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''   )





class 		__SCREAMING_SNAKE_CASE							(			lowercase__      ):







				def __init__(       self     :		int		,					UpperCAmelCase__     :		List[int]   ):
										'''simple docstring'''
										super(UpperCAmelCase__		,					self   ).__init__()

										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ) or len(UpperCAmelCase__   ) == 0:
																raise ValueError(F'''`token_ids` has to be a non-empty list, but is {token_ids}.'''   )
										if any((not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ) or token_id < 0) for token_id in token_ids   ):
																raise ValueError(F'''Each list in `token_ids` has to be a list of positive integers, but is {token_ids}.'''   )

										lowercase :							Union[str, Any]    		=token_ids

										lowercase :							Tuple    		=len(self.token_ids   )
										lowercase :							Tuple    		=-1  # the index of the currently fulfilled step
										lowercase :							int    		=False







				def  lowerCamelCase_	(       self     :		int   ):
										'''simple docstring'''
										if self.completed:
																return None
										return self.token_ids[self.fulfilled_idx + 1]







				def  lowerCamelCase_	(       self     :		str		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																raise ValueError(F'''`token_id` has to be an `int`, but is {token_id} of type {type(UpperCAmelCase__   )}'''   )

										if self.completed:
																return False

										return token_id == self.token_ids[self.fulfilled_idx + 1]







				def  lowerCamelCase_	(       self     :		str		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																raise ValueError(F'''`token_id` has to be an `int`, but is {token_id} of type {type(UpperCAmelCase__   )}'''   )

										lowercase :							Any    		=False
										lowercase :							Optional[int]    		=False
										lowercase :							int    		=False

										if self.does_advance(UpperCAmelCase__   ):
																self.fulfilled_idx += 1
																lowercase :							Any    		=True
																if self.fulfilled_idx == (self.seqlen - 1):
																						lowercase :							List[str]    		=True
																lowercase :							List[Any]    		=completed
										else:
																# failed to make progress.
																lowercase :							Union[str, Any]    		=True
																self.reset()
										return stepped, completed, reset







				def  lowerCamelCase_	(       self     :		Any   ):
										'''simple docstring'''
										lowercase :							int    		=False
										lowercase :							Tuple    		=0







				def  lowerCamelCase_	(       self     :		Union[str, Any]   ):
										'''simple docstring'''
										return self.seqlen - (self.fulfilled_idx + 1)







				def  lowerCamelCase_	(       self     :		int		,					UpperCAmelCase__     :		int=False   ):
										'''simple docstring'''
										lowercase :							Dict    		=PhrasalConstraint(self.token_ids   )

										if stateful:
																lowercase :							Union[str, Any]    		=self.seqlen
																lowercase :							Optional[Any]    		=self.fulfilled_idx
																lowercase :							List[str]    		=self.completed

										return new_constraint





class 		__SCREAMING_SNAKE_CASE							:







				def __init__(       self     :		Any		,					UpperCAmelCase__     :		List[List[int]]		,					UpperCAmelCase__     :		Dict=True   ):
										'''simple docstring'''
										lowercase :							str    		=max([len(UpperCAmelCase__   ) for one in nested_token_ids]   )

										lowercase :							Any    		={}
										for token_ids in nested_token_ids:
																lowercase :							Any    		=root
																for tidx, token_id in enumerate(UpperCAmelCase__   ):
																						if token_id not in level:
																												lowercase :							int    		={}

																						lowercase :							Union[str, Any]    		=level[token_id]

										if no_subsets and self.has_subsets(UpperCAmelCase__		,					UpperCAmelCase__   ):
																raise ValueError(
																    '''Each list in `nested_token_ids` can\'t be a complete subset of another list, but is'''
																    F''' {nested_token_ids}.'''   )

										lowercase :							Dict    		=root







				def  lowerCamelCase_	(       self     :		int		,					UpperCAmelCase__     :		Dict   ):
										'''simple docstring'''
										lowercase :							Any    		=self.trie

										for current_token in current_seq:
																lowercase :							List[str]    		=start[current_token]

										lowercase :							Optional[Any]    		=list(start.keys()   )

										return next_tokens







				def  lowerCamelCase_	(       self     :		str		,					UpperCAmelCase__     :		List[str]   ):
										'''simple docstring'''
										lowercase :							Union[str, Any]    		=self.next_tokens(UpperCAmelCase__   )

										return len(UpperCAmelCase__   ) == 0







				def  lowerCamelCase_	(       self     :		Optional[Any]		,					UpperCAmelCase__     :		Optional[int]   ):
										'''simple docstring'''
										lowercase :							Any    		=list(root.values()   )
										if len(UpperCAmelCase__   ) == 0:
																return 1
										else:
																return sum([self.count_leaves(UpperCAmelCase__   ) for nn in next_nodes]   )







				def  lowerCamelCase_	(       self     :		Dict		,					UpperCAmelCase__     :		Dict		,					UpperCAmelCase__     :		Dict   ):
										'''simple docstring'''
										lowercase :							List[str]    		=self.count_leaves(UpperCAmelCase__   )
										return len(UpperCAmelCase__   ) != leaf_count





class 		__SCREAMING_SNAKE_CASE							(			lowercase__      ):







				def __init__(       self     :		List[str]		,					UpperCAmelCase__     :		List[List[int]]   ):
										'''simple docstring'''
										super(UpperCAmelCase__		,					self   ).__init__()

										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ) or len(UpperCAmelCase__   ) == 0:
																raise ValueError(F'''`nested_token_ids` has to be a non-empty list, but is {nested_token_ids}.'''   )
										if any(not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ) for token_ids in nested_token_ids   ):
																raise ValueError(F'''`nested_token_ids` has to be a list of lists, but is {nested_token_ids}.'''   )
										if any(
										    any((not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ) or token_id < 0) for token_id in token_ids   )
										    for token_ids in nested_token_ids   ):
																raise ValueError(
																    F'''Each list in `nested_token_ids` has to be a list of positive integers, but is {nested_token_ids}.'''   )

										lowercase :							Any    		=DisjunctiveTrie(UpperCAmelCase__   )
										lowercase :							Tuple    		=nested_token_ids

										lowercase :							Dict    		=self.trie.max_height
										lowercase :							List[str]    		=[]
										lowercase :							str    		=False







				def  lowerCamelCase_	(       self     :		Optional[int]   ):
										'''simple docstring'''
										lowercase :							Any    		=self.trie.next_tokens(self.current_seq   )

										if len(UpperCAmelCase__   ) == 0:
																return None
										else:
																return token_list







				def  lowerCamelCase_	(       self     :		int		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																raise ValueError(F'''`token_id` is supposed to be type `int`, but is {token_id} of type {type(UpperCAmelCase__   )}'''   )

										lowercase :							Union[str, Any]    		=self.trie.next_tokens(self.current_seq   )

										return token_id in next_tokens







				def  lowerCamelCase_	(       self     :		Tuple		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																raise ValueError(F'''`token_id` is supposed to be type `int`, but is {token_id} of type {type(UpperCAmelCase__   )}'''   )

										lowercase :							Any    		=False
										lowercase :							Any    		=False
										lowercase :							Optional[Any]    		=False

										if self.does_advance(UpperCAmelCase__   ):
																self.current_seq.append(UpperCAmelCase__   )
																lowercase :							Dict    		=True
										else:
																lowercase :							Tuple    		=True
																self.reset()

										lowercase :							Union[str, Any]    		=self.trie.reached_leaf(self.current_seq   )
										lowercase :							int    		=completed

										return stepped, completed, reset







				def  lowerCamelCase_	(       self     :		Any   ):
										'''simple docstring'''
										lowercase :							int    		=False
										lowercase :							Tuple    		=[]







				def  lowerCamelCase_	(       self     :		Dict   ):
										'''simple docstring'''
										if self.completed:
																# since this can be completed without reaching max height
																return 0
										else:
																return self.seqlen - len(self.current_seq   )







				def  lowerCamelCase_	(       self     :		Dict		,					UpperCAmelCase__     :		Any=False   ):
										'''simple docstring'''
										lowercase :							Dict    		=DisjunctiveConstraint(self.token_ids   )

										if stateful:
																lowercase :							Union[str, Any]    		=self.seqlen
																lowercase :							int    		=self.current_seq
																lowercase :							Dict    		=self.completed

										return new_constraint





class 		__SCREAMING_SNAKE_CASE							:







				def __init__(       self     :		int		,					UpperCAmelCase__     :		List[Constraint]   ):
										'''simple docstring'''
										lowercase :							List[str]    		=constraints

										# max # of steps required to fulfill a given constraint
										lowercase :							str    		=max([c.seqlen for c in constraints]   )
										lowercase :							Any    		=len(UpperCAmelCase__   )
										lowercase :							Union[str, Any]    		=False

										self.init_state()







				def  lowerCamelCase_	(       self     :		str   ):
										'''simple docstring'''
										lowercase :							List[str]    		=[]
										lowercase :							Optional[Any]    		=None
										lowercase :							List[Any]    		=[constraint.copy(stateful=UpperCAmelCase__   ) for constraint in self.constraints]







				def  lowerCamelCase_	(       self     :		List[str]   ):
										'''simple docstring'''
										lowercase :							List[Any]    		=0
										if self.inprogress_constraint:
																# extra points for having a constraint mid-fulfilled
																add += self.max_seqlen - self.inprogress_constraint.remaining()

										return (len(self.complete_constraints   ) * self.max_seqlen) + add







				def  lowerCamelCase_	(       self     :		Union[str, Any]   ):
										'''simple docstring'''
										lowercase :							int    		=[]
										if self.inprogress_constraint is None:
																for constraint in self.pending_constraints:  # "pending" == "unfulfilled yet"
																						lowercase :							List[str]    		=constraint.advance()
																						if isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																												token_list.append(UpperCAmelCase__   )
																						elif isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																												token_list.extend(UpperCAmelCase__   )
										else:
																lowercase :							str    		=self.inprogress_constraint.advance()
																if isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																						token_list.append(UpperCAmelCase__   )
																elif isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																						token_list.extend(UpperCAmelCase__   )

										if len(UpperCAmelCase__   ) == 0:
																return None
										else:
																return token_list







				def  lowerCamelCase_	(       self     :		Union[str, Any]		,					UpperCAmelCase__     :		Optional[List[int]]   ):
										'''simple docstring'''
										self.init_state()

										if token_ids is not None:
																for token in token_ids:
																						# completes or steps **one** constraint
																						lowercase		,	lowercase :							Optional[Any]    		=self.add(UpperCAmelCase__   )

																						# the entire list of constraints are fulfilled
																						if self.completed:
																												break







				def  lowerCamelCase_	(       self     :		List[str]		,					UpperCAmelCase__     :		int   ):
										'''simple docstring'''
										if not isinstance(UpperCAmelCase__		,					UpperCAmelCase__   ):
																raise ValueError(F'''`token_id` should be an `int`, but is `{token_id}`.'''   )

										lowercase		,	lowercase :							List[Any]    		=False, False

										if self.completed:
																lowercase :							Tuple    		=True
																lowercase :							Union[str, Any]    		=False
																return complete, stepped

										if self.inprogress_constraint is not None:
																# In the middle of fulfilling a constraint. If the `token_id` *does* makes an incremental progress to current
																# job, simply update the state

																lowercase		,	lowercase		,	lowercase :							Union[str, Any]    		=self.inprogress_constraint.update(UpperCAmelCase__   )
																if reset:
																						# 1. If the next token breaks the progress, then we must restart.
																						#     e.g. constraint = "I love pies" and sequence so far is "I love" but `token_id` == "books".

																						#     But that doesn't mean we self.init_state(), since we only reset the state for this particular
																						#     constraint, not the full list of constraints.

																						self.pending_constraints.append(self.inprogress_constraint.copy(stateful=UpperCAmelCase__   )   )
																						lowercase :							List[str]    		=None

																if complete:
																						# 2. If the next token completes the constraint, move it to completed list, set
																						#     inprogress to None. If there are no pending constraints either, then this full list of constraints
																						#     is complete.

																						self.complete_constraints.append(self.inprogress_constraint   )
																						lowercase :							Optional[Any]    		=None

																						if len(self.pending_constraints   ) == 0:
																												# we're done!
																												lowercase :							int    		=True

										else:
																# Not in the middle of fulfilling a constraint. So does this `token_id` helps us step towards any of our list
																# of constraints?

																for cidx, pending_constraint in enumerate(self.pending_constraints   ):
																						if pending_constraint.does_advance(UpperCAmelCase__   ):
																												lowercase		,	lowercase		,	lowercase :							List[Any]    		=pending_constraint.update(UpperCAmelCase__   )

																												if not stepped:
																																		raise Exception(
																																		    '''`constraint.update(token_id)` is not yielding incremental progress, '''
																																		    '''even though `constraint.does_advance(token_id)` is true.'''   )

																												if complete:
																																		self.complete_constraints.append(UpperCAmelCase__   )
																																		lowercase :							Union[str, Any]    		=None

																												if not complete and stepped:
																																		lowercase :							Any    		=pending_constraint

																												if complete or stepped:
																																		# If we made any progress at all, then it's at least not a "pending constraint".

																																		lowercase :							int    		=(
																																		    self.pending_constraints[:cidx] + self.pending_constraints[cidx + 1 :]
																																		)

																																		if len(self.pending_constraints   ) == 0 and self.inprogress_constraint is None:
																																								# If there's no longer any pending after this and no inprogress either, then we must be
																																								# complete.

																																								lowercase :							List[Any]    		=True

																																		break  # prevent accidentally stepping through multiple constraints with just one token.

										return complete, stepped







				def  lowerCamelCase_	(       self     :		int		,					UpperCAmelCase__     :		Optional[int]=True   ):
										'''simple docstring'''
										lowercase :							int    		=ConstraintListState(self.constraints   )  # we actually never though self.constraints objects
										# throughout this process. So it's at initialization state.

										if stateful:
																lowercase :							Tuple    		=[
																    constraint.copy(stateful=UpperCAmelCase__   ) for constraint in self.complete_constraints
																]
																if self.inprogress_constraint is not None:
																						lowercase :							Dict    		=self.inprogress_constraint.copy(stateful=UpperCAmelCase__   )
																lowercase :							int    		=[constraint.copy() for constraint in self.pending_constraints]

										return new_state








'''simple docstring'''





def 				_lowerCAmelCase			(   __magic_name__						:     int = 600851475143						)				->  int:

						try:
												lowercase :							Any    		=int(__magic_name__						)
						except (TypeError, ValueError):
												raise TypeError('''Parameter n must be int or castable to int.'''						)
						if n <= 0:
												raise ValueError('''Parameter n must be greater than or equal to one.'''						)
						lowercase :							Optional[Any]    		=2
						lowercase :							Dict    		=0
						if n == 2:
												return 2
						while n > 2:
												while n % i != 0:
																		i += 1
												lowercase :							Union[str, Any]    		=i
												while n % i == 0:
																		lowercase :							Optional[int]    		=n // i
												i += 1
						return int(__magic_name__						)


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





