'''simple docstring'''






from __future__ import annotations






def  UpperCamelCase__					(					_lowercase    :				str   ,    _lowercase    :				str     )							->	bool:
  __UpperCAmelCase:					int		= get_failure_array(_lowercase     )

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

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






def  UpperCamelCase__					(					_lowercase    :				str     )							->	list[int]:
  __UpperCAmelCase:					int		= [0]
  __UpperCAmelCase:					List[Any]		= 0
  __UpperCAmelCase:					int		= 1
  while j < len(_lowercase     ):
    if pattern[i] == pattern[j]:
      i += 1
    elif i > 0:
      __UpperCAmelCase:					Any		= failure[i - 1]
      continue
    j += 1
    failure.append(_lowercase     )
  return failure


if __name__ == "__main__":
    # Test 1)
    SCREAMING_SNAKE_CASE_	   =			'abc1abc12'
    SCREAMING_SNAKE_CASE_	   =			'alskfjaldsabc1abc1abc12k23adsfabcabc'
    SCREAMING_SNAKE_CASE_	   =			'alskfjaldsk23adsfabcabc'
    assert kmp(pattern, texta) and not kmp(pattern, texta)

    # Test 2)
    SCREAMING_SNAKE_CASE_	   =			'ABABX'
    SCREAMING_SNAKE_CASE_	   =			'ABABZABABYABABX'
    assert kmp(pattern, text)

    # Test 3)
    SCREAMING_SNAKE_CASE_	   =			'AAAB'
    SCREAMING_SNAKE_CASE_	   =			'ABAAAAAB'
    assert kmp(pattern, text)

    # Test 4)
    SCREAMING_SNAKE_CASE_	   =			'abcdabcy'
    SCREAMING_SNAKE_CASE_	   =			'abcxabcdabxabcdabcdabcy'
    assert kmp(pattern, text)

    # Test 5)
    SCREAMING_SNAKE_CASE_	   =			'aabaabaaa'
    assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]
'''simple docstring'''






from __future__ import annotations






def  UpperCamelCase__					(					_lowercase    :				list[int]   ,    _lowercase    :				int   ,    _lowercase    :				int   ,    _lowercase    :				int     )							->	None:
  if (direction == 1 and array[indexa] > array[indexa]) or (
      direction == 0 and array[indexa] < array[indexa]
  ):
    __UpperCAmelCase, __UpperCAmelCase:					str		= array[indexa], array[indexa]






def  UpperCamelCase__					(					_lowercase    :				list[int]   ,    _lowercase    :				int   ,    _lowercase    :				int   ,    _lowercase    :				int     )							->	None:
  if length > 1:
    __UpperCAmelCase:					List[str]		= int(length / 2     )
    for i in range(_lowercase   ,    low + middle     ):
      comp_and_swap(_lowercase   ,    _lowercase   ,    i + middle   ,    _lowercase     )
    bitonic_merge(_lowercase   ,    _lowercase   ,    _lowercase   ,    _lowercase     )
    bitonic_merge(_lowercase   ,    low + middle   ,    _lowercase   ,    _lowercase     )






def  UpperCamelCase__					(					_lowercase    :				list[int]   ,    _lowercase    :				int   ,    _lowercase    :				int   ,    _lowercase    :				int     )							->	None:
  if length > 1:
    __UpperCAmelCase:					Any		= int(length / 2     )
    bitonic_sort(_lowercase   ,    _lowercase   ,    _lowercase   ,    1     )
    bitonic_sort(_lowercase   ,    low + middle   ,    _lowercase   ,    0     )
    bitonic_merge(_lowercase   ,    _lowercase   ,    _lowercase   ,    _lowercase     )


if __name__ == "__main__":
    SCREAMING_SNAKE_CASE_	   =			input('Enter numbers separated by a comma:\n').strip()
    SCREAMING_SNAKE_CASE_	   =			[int(item.strip()) for item in user_input.split(',')]

    bitonic_sort(unsorted, 0, len(unsorted), 1)
    print('\nSorted array in ascending order is: ', end='')
    print(*unsorted, sep=', ')

    bitonic_merge(unsorted, 0, len(unsorted), 0)
    print('Sorted array in descending order is: ', end='')
    print(*unsorted, sep=', ')