



def      _A				(UpperCamelCase		:      str      ,			UpperCamelCase		:      int )  ->list:



			'''simple docstring'''







			lowerCamelCase__ :      Union[str, Any]								=		word.split()

			def justify(UpperCamelCase		:      list      ,			UpperCamelCase		:      int      ,			UpperCamelCase		:      int ) -> str:
						lowerCamelCase__ :      Any								=		max_width - width
						lowerCamelCase__ :      Optional[int]								=		len(UpperCamelCase )
						if len(UpperCamelCase ) == 1:
									# if there is only word in line
									# just insert overall_spaces_count for the remainder of line
									return line[0] + " " * overall_spaces_count
						else:
									lowerCamelCase__ :      List[str]								=		words_count - 1
									# num_spaces_between_words_list[i] : tells you to insert
									# num_spaces_between_words_list[i] spaces
									# after word on line[i]
									lowerCamelCase__ :      Optional[Any]								=		spaces_to_insert_between_words * [
									    overall_spaces_count // spaces_to_insert_between_words
									]
									lowerCamelCase__ :      Any								=		(
									    overall_spaces_count % spaces_to_insert_between_words
									)
									# distribute spaces via round robin to the left words
									for i in range(UpperCamelCase ):
												num_spaces_between_words_list[i] += 1
									lowerCamelCase__ :      Any								=		[]
									for i in range(UpperCamelCase ):
												# add the word
												aligned_words_list.append(line[i] )
												# add the spaces to insert
												aligned_words_list.append(num_spaces_between_words_list[i] * """ """ )
									# just add the last word to the sentence
									aligned_words_list.append(line[-1] )
									# join the aligned words list to form a justified line
									return "".join(UpperCamelCase )

			lowerCamelCase__ :      Optional[int]								=		[]
			lowerCamelCase__ :      list[str]								=		[]
			lowerCamelCase__ :      Union[str, Any]								=		0
			for word in words:
						if width + len(UpperCamelCase ) + len(UpperCamelCase ) <= max_width:
									# keep adding words until we can fill out max_width
									# width = sum of length of all words (without overall_spaces_count)
									# len(word) = length of current word
									# len(line) = number of overall_spaces_count to insert between words
									line.append(UpperCamelCase )
									width += len(UpperCamelCase )
						else:
									# justify the line and add it to result
									answer.append(justify(UpperCamelCase      ,			UpperCamelCase      ,			UpperCamelCase ) )
									# reset new line and new width
									lowerCamelCase__							,lowerCamelCase__ :      Optional[int]								=		[word], len(UpperCamelCase )
			lowerCamelCase__ :      Optional[int]								=		max_width - width - len(UpperCamelCase )
			answer.append(""" """.join(UpperCamelCase ) + (remaining_spaces + 1) * """ """ )
			return answer


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

				testmod()








from __future__ import annotations






def      _A				(UpperCamelCase		:      str      ,			UpperCamelCase		:      list[str] | None = None )  ->list[list[str]]:



			'''simple docstring'''







			lowerCamelCase__ :      List[str]								=		word_bank or []
			# create a table
			lowerCamelCase__ :      int								=		len(UpperCamelCase ) + 1

			lowerCamelCase__ :      list[list[list[str]]]								=		[]
			for _ in range(UpperCamelCase ):
						table.append([] )
			# seed value
			lowerCamelCase__ :      Tuple								=		[[]]  # because empty string has empty combination

			# iterate through the indices
			for i in range(UpperCamelCase ):
						# condition
						if table[i] != []:
									for word in word_bank:
												# slice condition
												if target[i : i + len(UpperCamelCase )] == word:
															lowerCamelCase__ :      list[list[str]]								=		[
															    [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(UpperCamelCase )] += new_combinations

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

			return table[len(UpperCamelCase )]


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'''],
				    )
				)



