Coco the Monkey has a strange, unhealthy obsession with strings.
Coco the Monkey has suddenly decided that a string is cute, if it appears as a substring in another string S as a prefix, suffix and somewhere in the middle of string S (not as a prefix or suffix).
Please help Coco the Monkey find the longest string that is cute in string S.
The only line of input will contain one string, S. S will contain only lowercase english alphabets and no other characters.
Output a single string, the longest string that Coco the Monkey considers cute. If no such string exists, output -1.
Subtask 1 (33%): 1 ≤ | S | ≤ 1000.
Subtask 2 (67%): 1 ≤ | S | ≤ 1 000 000.
Subtask 3 (0%): Sample Testcases
Sample Testcase 1