
"""simple docstring"""




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





class 			snake_case  (				__lowercase ):

							def __init__(self     ):

									"""simple docstring"""







									self.test()

							def _lowercase       (self     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			0
									SCREAMING_SNAKE_CASE_    			=			False
									while not completed:
											if counter == 1:
													self.reset()
											SCREAMING_SNAKE_CASE_    			=			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.'''     )

											SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_    			=			self.update(SCREAMING_SNAKE_CASE_     )
											counter += 1

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

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

							@abstractmethod
							def _lowercase       (self     ):

									"""simple docstring"""







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

							@abstractmethod
							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







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

							@abstractmethod
							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







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

							@abstractmethod
							def _lowercase       (self     ):

									"""simple docstring"""







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

							@abstractmethod
							def _lowercase       (self     ):

									"""simple docstring"""







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







							@abstractmethod
							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_=False     ):

									"""simple docstring"""







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







class 			snake_case  (				__lowercase ):

							def __init__(self							,							SCREAMING_SNAKE_CASE_     ):

									"""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}.'     )

									SCREAMING_SNAKE_CASE_    			=			token_ids

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

							def _lowercase       (self     ):

									"""simple docstring"""







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

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""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 _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""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_     )}'     )

									SCREAMING_SNAKE_CASE_    			=			False
									SCREAMING_SNAKE_CASE_    			=			False
									SCREAMING_SNAKE_CASE_    			=			False

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

							def _lowercase       (self     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			False
									SCREAMING_SNAKE_CASE_    			=			0

							def _lowercase       (self     ):

									"""simple docstring"""







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







							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_=False     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			PhrasalConstraint(self.token_ids     )

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

									return new_constraint







class 			snake_case  :

							def __init__(self							,							SCREAMING_SNAKE_CASE_							,							SCREAMING_SNAKE_CASE_=True     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			max([len(SCREAMING_SNAKE_CASE_     ) for one in nested_token_ids]     )

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

													SCREAMING_SNAKE_CASE_    			=			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}.'     )

									SCREAMING_SNAKE_CASE_    			=			root

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			self.trie

									for current_token in current_seq:
											SCREAMING_SNAKE_CASE_    			=			start[current_token]

									SCREAMING_SNAKE_CASE_    			=			list(start.keys()     )

									return next_tokens

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			self.next_tokens(SCREAMING_SNAKE_CASE_     )

									return len(SCREAMING_SNAKE_CASE_     ) == 0

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			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 _lowercase       (self							,							SCREAMING_SNAKE_CASE_							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			self.count_leaves(SCREAMING_SNAKE_CASE_     )
									return len(SCREAMING_SNAKE_CASE_     ) != leaf_count







class 			snake_case  (				__lowercase ):

							def __init__(self							,							SCREAMING_SNAKE_CASE_     ):

									"""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}.'     )

									SCREAMING_SNAKE_CASE_    			=			DisjunctiveTrie(SCREAMING_SNAKE_CASE_     )
									SCREAMING_SNAKE_CASE_    			=			nested_token_ids

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

							def _lowercase       (self     ):

									"""simple docstring"""







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

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

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""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_     )}'     )

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

									return token_id in next_tokens

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""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_     )}'     )

									SCREAMING_SNAKE_CASE_    			=			False
									SCREAMING_SNAKE_CASE_    			=			False
									SCREAMING_SNAKE_CASE_    			=			False

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

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

									return stepped, completed, reset

							def _lowercase       (self     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			False
									SCREAMING_SNAKE_CASE_    			=			[]

							def _lowercase       (self     ):

									"""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 _lowercase       (self							,							SCREAMING_SNAKE_CASE_=False     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			DisjunctiveConstraint(self.token_ids     )

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

									return new_constraint







class 			snake_case  :

							def __init__(self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			constraints

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

									self.init_state()

							def _lowercase       (self     ):

									"""simple docstring"""







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

							def _lowercase       (self     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			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 _lowercase       (self     ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_    			=			[]
									if self.inprogress_constraint is None:
											for constraint in self.pending_constraints:  # "pending" == "unfulfilled yet"
													SCREAMING_SNAKE_CASE_    			=			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:
											SCREAMING_SNAKE_CASE_    			=			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 _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







									self.init_state()

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

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

							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_     ):

									"""simple docstring"""







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

									SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_    			=			False, False

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

											SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_    			=			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_     )     )
													SCREAMING_SNAKE_CASE_    			=			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     )
													SCREAMING_SNAKE_CASE_    			=			None

													if len(self.pending_constraints     ) == 0:
															# we're done!
															SCREAMING_SNAKE_CASE_    			=			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_     ):
															SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_			,SCREAMING_SNAKE_CASE_    			=			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_     )
																	SCREAMING_SNAKE_CASE_    			=			None

															if not complete and stepped:
																	SCREAMING_SNAKE_CASE_    			=			pending_constraint

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

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

																			SCREAMING_SNAKE_CASE_    			=			True

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

									return complete, stepped







							def _lowercase       (self							,							SCREAMING_SNAKE_CASE_=True     ):

									"""simple docstring"""







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

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

									return new_state

"""simple docstring"""




from __future__ import annotations



def 							_lowerCamelCase			(			__a,				__a = None     ):
		SCREAMING_SNAKE_CASE_    			=			word_bank or []
		# create a table
		SCREAMING_SNAKE_CASE_    			=			len(__a     ) + 1

		SCREAMING_SNAKE_CASE_    			=			[]
		for _ in range(__a     ):
				table.append([]     )
		# seed value
		SCREAMING_SNAKE_CASE_    			=			[[]]  # because empty string has empty combination

		# iterate through the indices
		for i in range(__a     ):
				# condition
				if table[i] != []:
						for word in word_bank:
								# slice condition
								if target[i : i + len(__a     )] == word:
										SCREAMING_SNAKE_CASE_    			=			[
										    [word, *way] for way in table[i]
										]
										# adds the word to every combination the current position holds
										# now,push that combination to the table[i+len(word)]
										table[i + len(__a     )] += new_combinations

    # combinations are in reverse order so reverse for better output
		for combination in table[len(__a     )]:
				combination.reverse()

		return table[len(__a     )]


if __name__ == "__main__":
						print(all_construct('jwajalapa', ['jwa', 'j', 'w', 'a', 'la', 'lapa']))
						print(all_construct('rajamati', ['s', 'raj', 'amat', 'raja', 'ma', 'i', 't']))
						print(
						    all_construct(
						        'hexagonosaurus',
						        ['h', 'ex', 'hex', 'ag', 'ago', 'ru', 'auru', 'rus', 'go', 'no', 'o', 's'],
						    )
						)