


'''simple docstring'''







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


class  lowerCAmelCase_						(       snake_case__      ):





		"""simple docstring"""



		def __init__(					self     :							Dict						):





							'''simple docstring'''

							self.test()

		def __a						(					self     :							int						):





							'''simple docstring'''

							__a       =   0
							__a       =   False
							while not completed:
												if counter == 1:
																	self.reset()
												__a       =   self.advance()
												if not self.does_advance(SCREAMING_SNAKE_CASE__						):
																	raise Exception(
																	    """Custom Constraint is not defined correctly. self.does_advance(self.advance()) must be true."""						)

												__a ,						__a ,						__a       =   self.update(SCREAMING_SNAKE_CASE__						)
												counter += 1

												if counter > 1_0_0_0_0:
																	raise Exception("""update() does not fulfill the constraint."""						)

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

		@abstractmethod
		def __a						(					self     :							Any						):





							'''simple docstring'''

							raise NotImplementedError(
							    f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''						)

		@abstractmethod
		def __a						(					self     :							Dict				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							raise NotImplementedError(
							    f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''						)

		@abstractmethod
		def __a						(					self     :							Optional[int]				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							raise NotImplementedError(
							    f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''						)

		@abstractmethod
		def __a						(					self     :							List[Any]						):





							'''simple docstring'''

							raise NotImplementedError(
							    f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''						)

		@abstractmethod
		def __a						(					self     :							List[Any]						):





							'''simple docstring'''

							raise NotImplementedError(
							    f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''						)


		@abstractmethod
		def __a						(					self     :							Optional[int]				,							SCREAMING_SNAKE_CASE__     :							Tuple=False						):





							'''simple docstring'''

							raise NotImplementedError(
							    f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''						)


class  lowerCAmelCase_						(       snake_case__      ):





		"""simple docstring"""



		def __init__(					self     :							List[Any]				,							SCREAMING_SNAKE_CASE__     :							List[int]						):





							'''simple docstring'''

							super(SCREAMING_SNAKE_CASE__				,							self						).__init__()

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						) or len(SCREAMING_SNAKE_CASE__						) == 0:
												raise ValueError(f'''`token_ids` has to be a non-empty list, but is {token_ids}.'''						)
							if any((not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						) 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}.'''						)

							__a       =   token_ids

							__a       =   len(self.token_ids						)
							__a       =   -1  # the index of the currently fulfilled step
							__a       =   False

		def __a						(					self     :							Optional[int]						):





							'''simple docstring'''

							if self.completed:
												return None
							return self.token_ids[self.fulfilled_idx + 1]

		def __a						(					self     :							Optional[Any]				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
												raise ValueError(f'''`token_id` has to be an `int`, but is {token_id} of type {type(SCREAMING_SNAKE_CASE__						)}'''						)

							if self.completed:
												return False

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

		def __a						(					self     :							List[Any]				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
												raise ValueError(f'''`token_id` has to be an `int`, but is {token_id} of type {type(SCREAMING_SNAKE_CASE__						)}'''						)

							__a       =   False
							__a       =   False
							__a       =   False

							if self.does_advance(SCREAMING_SNAKE_CASE__						):
												self.fulfilled_idx += 1
												__a       =   True
												if self.fulfilled_idx == (self.seqlen - 1):
																	__a       =   True
												__a       =   completed
							else:
												# failed to make progress.
												__a       =   True
												self.reset()
							return stepped, completed, reset

		def __a						(					self     :							List[Any]						):





							'''simple docstring'''

							__a       =   False
							__a       =   0

		def __a						(					self     :							Any						):





							'''simple docstring'''

							return self.seqlen - (self.fulfilled_idx + 1)


		def __a						(					self     :							Dict				,							SCREAMING_SNAKE_CASE__     :							Optional[Any]=False						):





							'''simple docstring'''

							__a       =   PhrasalConstraint(self.token_ids						)

							if stateful:
												__a       =   self.seqlen
												__a       =   self.fulfilled_idx
												__a       =   self.completed

							return new_constraint


class  lowerCAmelCase_						:





		"""simple docstring"""



		def __init__(					self     :							List[str]				,							SCREAMING_SNAKE_CASE__     :							List[List[int]]				,							SCREAMING_SNAKE_CASE__     :							int=True						):





							'''simple docstring'''

							__a       =   max([len(SCREAMING_SNAKE_CASE__						) for one in nested_token_ids]						)

							__a       =   {}
							for token_ids in nested_token_ids:
												__a       =   root
												for tidx, token_id in enumerate(SCREAMING_SNAKE_CASE__						):
																	if token_id not in level:
																						__a       =   {}

																	__a       =   level[token_id]

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

							__a       =   root

		def __a						(					self     :							Tuple				,							SCREAMING_SNAKE_CASE__     :							List[str]						):





							'''simple docstring'''

							__a       =   self.trie

							for current_token in current_seq:
												__a       =   start[current_token]

							__a       =   list(start.keys()						)

							return next_tokens

		def __a						(					self     :							Optional[int]				,							SCREAMING_SNAKE_CASE__     :							Union[str, Any]						):





							'''simple docstring'''

							__a       =   self.next_tokens(SCREAMING_SNAKE_CASE__						)

							return len(SCREAMING_SNAKE_CASE__						) == 0

		def __a						(					self     :							Dict				,							SCREAMING_SNAKE_CASE__     :							List[Any]						):





							'''simple docstring'''

							__a       =   list(root.values()						)
							if len(SCREAMING_SNAKE_CASE__						) == 0:
												return 1
							else:
												return sum([self.count_leaves(SCREAMING_SNAKE_CASE__						) for nn in next_nodes]						)


		def __a						(					self     :							int				,							SCREAMING_SNAKE_CASE__     :							List[str]				,							SCREAMING_SNAKE_CASE__     :							Tuple						):





							'''simple docstring'''

							__a       =   self.count_leaves(SCREAMING_SNAKE_CASE__						)
							return len(SCREAMING_SNAKE_CASE__						) != leaf_count


class  lowerCAmelCase_						(       snake_case__      ):





		"""simple docstring"""



		def __init__(					self     :							Optional[Any]				,							SCREAMING_SNAKE_CASE__     :							List[List[int]]						):





							'''simple docstring'''

							super(SCREAMING_SNAKE_CASE__				,							self						).__init__()

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						) or len(SCREAMING_SNAKE_CASE__						) == 0:
												raise ValueError(f'''`nested_token_ids` has to be a non-empty list, but is {nested_token_ids}.'''						)
							if any(not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						) 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(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						) 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}.'''						)

							__a       =   DisjunctiveTrie(SCREAMING_SNAKE_CASE__						)
							__a       =   nested_token_ids

							__a       =   self.trie.max_height
							__a       =   []
							__a       =   False

		def __a						(					self     :							Any						):





							'''simple docstring'''

							__a       =   self.trie.next_tokens(self.current_seq						)

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

		def __a						(					self     :							Tuple				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
												raise ValueError(f'''`token_id` is supposed to be type `int`, but is {token_id} of type {type(SCREAMING_SNAKE_CASE__						)}'''						)

							__a       =   self.trie.next_tokens(self.current_seq						)

							return token_id in next_tokens

		def __a						(					self     :							Any				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
												raise ValueError(f'''`token_id` is supposed to be type `int`, but is {token_id} of type {type(SCREAMING_SNAKE_CASE__						)}'''						)

							__a       =   False
							__a       =   False
							__a       =   False

							if self.does_advance(SCREAMING_SNAKE_CASE__						):
												self.current_seq.append(SCREAMING_SNAKE_CASE__						)
												__a       =   True
							else:
												__a       =   True
												self.reset()

							__a       =   self.trie.reached_leaf(self.current_seq						)
							__a       =   completed

							return stepped, completed, reset

		def __a						(					self     :							Optional[int]						):





							'''simple docstring'''

							__a       =   False
							__a       =   []

		def __a						(					self     :							str						):





							'''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 __a						(					self     :							int				,							SCREAMING_SNAKE_CASE__     :							Optional[int]=False						):





							'''simple docstring'''

							__a       =   DisjunctiveConstraint(self.token_ids						)

							if stateful:
												__a       =   self.seqlen
												__a       =   self.current_seq
												__a       =   self.completed

							return new_constraint


class  lowerCAmelCase_						:





		"""simple docstring"""



		def __init__(					self     :							Union[str, Any]				,							SCREAMING_SNAKE_CASE__     :							List[Constraint]						):





							'''simple docstring'''

							__a       =   constraints

							# max # of steps required to fulfill a given constraint
							__a       =   max([c.seqlen for c in constraints]						)
							__a       =   len(SCREAMING_SNAKE_CASE__						)
							__a       =   False

							self.init_state()

		def __a						(					self     :							Tuple						):





							'''simple docstring'''

							__a       =   []
							__a       =   None
							__a       =   [constraint.copy(stateful=SCREAMING_SNAKE_CASE__						) for constraint in self.constraints]

		def __a						(					self     :							int						):





							'''simple docstring'''

							__a       =   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 __a						(					self     :							Dict						):





							'''simple docstring'''

							__a       =   []
							if self.inprogress_constraint is None:
												for constraint in self.pending_constraints:  # "pending" == "unfulfilled yet"
																	__a       =   constraint.advance()
																	if isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
																						token_list.append(SCREAMING_SNAKE_CASE__						)
																	elif isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
																						token_list.extend(SCREAMING_SNAKE_CASE__						)
							else:
												__a       =   self.inprogress_constraint.advance()
												if isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
																	token_list.append(SCREAMING_SNAKE_CASE__						)
												elif isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
																	token_list.extend(SCREAMING_SNAKE_CASE__						)

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

		def __a						(					self     :							Optional[Any]				,							SCREAMING_SNAKE_CASE__     :							Optional[List[int]]						):





							'''simple docstring'''

							self.init_state()

							if token_ids is not None:
												for token in token_ids:
																	# completes or steps **one** constraint
																	__a ,						__a       =   self.add(SCREAMING_SNAKE_CASE__						)

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

		def __a						(					self     :							Optional[int]				,							SCREAMING_SNAKE_CASE__     :							int						):





							'''simple docstring'''

							if not isinstance(SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__						):
												raise ValueError(f'''`token_id` should be an `int`, but is `{token_id}`.'''						)

							__a ,						__a       =   False, False

							if self.completed:
												__a       =   True
												__a       =   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

												__a ,						__a ,						__a       =   self.inprogress_constraint.update(SCREAMING_SNAKE_CASE__						)
												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=SCREAMING_SNAKE_CASE__						)						)
																	__a       =   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						)
																	__a       =   None

																	if len(self.pending_constraints						) == 0:
																						# we're done!
																						__a       =   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(SCREAMING_SNAKE_CASE__						):
																						__a ,						__a ,						__a       =   pending_constraint.update(SCREAMING_SNAKE_CASE__						)

																						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(SCREAMING_SNAKE_CASE__						)
																											__a       =   None

																						if not complete and stepped:
																											__a       =   pending_constraint

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

																											__a       =   (
																											    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.

																																__a       =   True

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

							return complete, stepped


		def __a						(					self     :							int				,							SCREAMING_SNAKE_CASE__     :							List[str]=True						):





							'''simple docstring'''

							__a       =   ConstraintListState(self.constraints						)  # we actually never though self.constraints objects
							# throughout this process. So it's at initialization state.

							if stateful:
												__a       =   [
												    constraint.copy(stateful=SCREAMING_SNAKE_CASE__						) for constraint in self.complete_constraints
												]
												if self.inprogress_constraint is not None:
																	__a       =   self.inprogress_constraint.copy(stateful=SCREAMING_SNAKE_CASE__						)
												__a       =   [constraint.copy() for constraint in self.pending_constraints]

							return new_state










'''simple docstring'''







SCREAMING_SNAKE_CASE_      =			0  # The first color of the flag.
SCREAMING_SNAKE_CASE_      =			1  # The second color of the flag.
SCREAMING_SNAKE_CASE_      =			2  # The third color of the flag.
SCREAMING_SNAKE_CASE_      =			(red, white, blue)




def        __lowercase						(      __SCREAMING_SNAKE_CASE		)				->					list:
     """simple docstring"""




     if not sequence:
          return []
     if len(__SCREAMING_SNAKE_CASE		) == 1:
          return list(__SCREAMING_SNAKE_CASE		)
     __a       =   0
     __a       =   len(__SCREAMING_SNAKE_CASE		) - 1
     __a       =   0
     while mid <= high:
          if sequence[mid] == colors[0]:
               __a ,						__a       =   sequence[mid], sequence[low]
               low += 1
               mid += 1
          elif sequence[mid] == colors[1]:
               mid += 1
          elif sequence[mid] == colors[2]:
               __a ,						__a       =   sequence[high], sequence[mid]
               high -= 1
          else:
               __a       =   F'''The elements inside the sequence must contains only {colors} values'''
               raise ValueError(__SCREAMING_SNAKE_CASE		)
     return sequence


if __name__ == "__main__":
 import doctest

 doctest.testmod()

 SCREAMING_SNAKE_CASE_      =			input('Enter numbers separated by commas:\n').strip()
 SCREAMING_SNAKE_CASE_      =			[int(item.strip()) for item in user_input.split(',')]
 print(f"""{dutch_national_flag_sort(unsorted)}""")






