from __future__ import annotations



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str				,  __UpperCamelCase					: str			)							->      bool:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   get_failure_array(__UpperCamelCase			)

  # 2) Step through text searching for pattern
  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   0, 0  # index into text, pattern
  while i < len(__UpperCamelCase			):
    if pattern[j] == text[i]:
      if j == (len(__UpperCamelCase			) - 1):
        return True
      j += 1

    # if this is a prefix in our pattern
    # just go back far enough to continue
    elif j > 0:
      SCREAMING_SNAKE_CASE__    							=   failure[j - 1]
      continue
    i += 1
  return False



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str			)							->      list[int]:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   [0]
  SCREAMING_SNAKE_CASE__    							=   0
  SCREAMING_SNAKE_CASE__    							=   1
  while j < len(__UpperCamelCase			):
    if pattern[i] == pattern[j]:
      i += 1
    elif i > 0:
      SCREAMING_SNAKE_CASE__    							=   failure[i - 1]
      continue
    j += 1
    failure.append(__UpperCamelCase			)
  return failure


if __name__ == "__main__":
   # Test 1)
   __lowerCamelCase    :				Dict							     =	'''abc1abc12'''
   __lowerCamelCase    :				int							     =	'''alskfjaldsabc1abc1abc12k23adsfabcabc'''
   __lowerCamelCase    :				Optional[Any]							     =	'''alskfjaldsk23adsfabcabc'''
   assert kmp(pattern, texta) and not kmp(pattern, texta)

   # Test 2)
   __lowerCamelCase    :				List[str]							     =	'''ABABX'''
   __lowerCamelCase    :				List[str]							     =	'''ABABZABABYABABX'''
   assert kmp(pattern, text)

   # Test 3)
   __lowerCamelCase    :				List[str]							     =	'''AAAB'''
   __lowerCamelCase    :				str							     =	'''ABAAAAAB'''
   assert kmp(pattern, text)

   # Test 4)
   __lowerCamelCase    :				Any							     =	'''abcdabcy'''
   __lowerCamelCase    :				Optional[Any]							     =	'''abcxabcdabxabcdabcdabcy'''
   assert kmp(pattern, text)

   # Test 5)
   __lowerCamelCase    :				Any							     =	'''aabaabaaa'''
   assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]

def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: int			)							->      int:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   [1]

  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   0, 0, 0
  SCREAMING_SNAKE_CASE__    							=   ugly_nums[ia] * 2
  SCREAMING_SNAKE_CASE__    							=   ugly_nums[ia] * 3
  SCREAMING_SNAKE_CASE__    							=   ugly_nums[ia] * 5

  for _ in range(1				,  __UpperCamelCase			):
    SCREAMING_SNAKE_CASE__    							=   min(__UpperCamelCase				,  __UpperCamelCase				,  __UpperCamelCase			)
    ugly_nums.append(__UpperCamelCase			)
    if next_num == next_a:
      ia += 1
      SCREAMING_SNAKE_CASE__    							=   ugly_nums[ia] * 2
    if next_num == next_a:
      ia += 1
      SCREAMING_SNAKE_CASE__    							=   ugly_nums[ia] * 3
    if next_num == next_a:
      ia += 1
      SCREAMING_SNAKE_CASE__    							=   ugly_nums[ia] * 5
  return ugly_nums[-1]


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

   testmod(verbose=True)
   print(F"""{ugly_numbers(200) = }""")
