"""simple docstring"""





def        a_  (   _lowerCAmelCase						:				list  ):





       '''simple docstring'''

       if len(_lowerCAmelCase  ) <= 1:
              return [tuple(_lowerCAmelCase  )]

       lowercase__    :	Optional[Any]     					=			[]

       def generate(_lowerCAmelCase						:				int     ,				_lowerCAmelCase						:				list  ):
              lowercase__    :	Optional[int]     					=			[0] * n
              res.append(tuple(_lowerCAmelCase  )  )

              lowercase__    :	List[Any]     					=			0
              while i < n:
                     if c[i] < i:
                            if i % 2 == 0:
                                   lowercase__					,   lowercase__    :	int     					=			arr[i], arr[0]
                            else:
                                   lowercase__					,   lowercase__    :	str     					=			arr[i], arr[c[i]]
                            res.append(tuple(_lowerCAmelCase  )  )
                            c[i] += 1
                            lowercase__    :	int     					=			0
                     else:
                            lowercase__    :	List[Any]     					=			0
                            i += 1

       generate(len(_lowerCAmelCase  )     ,				_lowerCAmelCase  )
       return res


if __name__ == "__main__":
       _UpperCamelCase     :		Dict											=					input("Enter numbers separated by a comma:\n").strip()
       _UpperCamelCase     :		Any											=					[int(item) for item in user_input.split(",")]
       print(heaps(arr))


"""simple docstring"""





def        a_  (   _lowerCAmelCase						:				str  ):





       '''simple docstring'''

       lowercase__    :	Any     					=			[0] * len(_lowerCAmelCase  )

       for i in range(1     ,				len(_lowerCAmelCase  )  ):
              # use last results for better performance - dynamic programming
              lowercase__    :	List[str]     					=			prefix_result[i - 1]
              while j > 0 and input_string[i] != input_string[j]:
                     lowercase__    :	Dict     					=			prefix_result[j - 1]

              if input_string[i] == input_string[j]:
                     j += 1
              lowercase__    :	Union[str, Any]     					=			j

       return prefix_result





def        a_  (   _lowerCAmelCase						:				str  ):





       '''simple docstring'''

       return max(prefix_function(_lowerCAmelCase  )  )


if __name__ == "__main__":
       import doctest

       doctest.testmod()

