def lowerCamelCase  (   SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    __UpperCamelCase     :Tuple			  =		[0 for i in range(len(SCREAMING_SNAKE_CASE	)	)]

    # initialize interval's left pointer and right pointer
    __UpperCamelCase  ,       __UpperCamelCase     :str			  =		0, 0

    for i in range(1  ,			len(SCREAMING_SNAKE_CASE	)	):
        # case when current index is inside the interval
        if i <= right_pointer:
            __UpperCamelCase     :Union[str, Any]			  =		min(right_pointer - i + 1  ,			z_result[i - left_pointer]	)
            __UpperCamelCase     :Tuple			  =		min_edge

        while go_next(SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
            z_result[i] += 1

        # if new index's result gives us more right interval,
        # we've to update left_pointer and right_pointer
        if i + z_result[i] - 1 > right_pointer:
            __UpperCamelCase  ,       __UpperCamelCase     :Union[str, Any]			  =		i, i + z_result[i] - 1

    return z_result



def lowerCamelCase  (   SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    return i + z_result[i] < len(SCREAMING_SNAKE_CASE	) and s[z_result[i]] == s[i + z_result[i]]



def lowerCamelCase  (   SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    __UpperCamelCase     :List[Any]			  =		0
    # concatenate 'pattern' and 'input_str' and call z_function
    # with concatenated string
    __UpperCamelCase     :Tuple			  =		z_function(pattern + input_str	)

    for val in z_result:
        # if value is greater then length of the pattern string
        # that means this index is starting position of substring
        # which is equal to pattern string
        if val >= len(SCREAMING_SNAKE_CASE	):
            answer += 1

    return answer


if __name__ == "__main__":
    import doctest

    doctest.testmod()






import random



def lowerCamelCase  (   SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    __UpperCamelCase     :Optional[Any]			  =		a[left_index]
    __UpperCamelCase     :Any			  =		left_index + 1
    for j in range(left_index + 1  ,			SCREAMING_SNAKE_CASE	):
        if a[j] < pivot:
            __UpperCamelCase  ,       __UpperCamelCase     :str			  =		a[i], a[j]
            i += 1
    __UpperCamelCase  ,       __UpperCamelCase     :Optional[int]			  =		a[i - 1], a[left_index]
    return i - 1



def lowerCamelCase  (   SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    if left < right:
        __UpperCamelCase     :int			  =		random.randint(SCREAMING_SNAKE_CASE  ,			right - 1	)
        __UpperCamelCase  ,       __UpperCamelCase     :List[str]			  =		(
            a[left],
            a[pivot],
        )  # switches the pivot with the left most bound
        __UpperCamelCase     :Dict			  =		partition(SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	)
        quick_sort_random(
            SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE  ,			SCREAMING_SNAKE_CASE	)  # recursive quicksort to the left of the pivot point
        quick_sort_random(
            SCREAMING_SNAKE_CASE  ,			pivot_index + 1  ,			SCREAMING_SNAKE_CASE	)  # recursive quicksort to the right of the pivot point



def lowerCamelCase  (   ):
    '''simple docstring'''







    __UpperCamelCase     :Tuple			  =		input('''Enter numbers separated by a comma:\n'''	).strip()
    __UpperCamelCase     :Union[str, Any]			  =		[int(SCREAMING_SNAKE_CASE	) for item in user_input.split(''','''	)]

    quick_sort_random(SCREAMING_SNAKE_CASE  ,			0  ,			len(SCREAMING_SNAKE_CASE	)	)

    print(SCREAMING_SNAKE_CASE	)


if __name__ == "__main__":
    main()





