- Time limit: 1.00 s
- Memory limit: 512 MB
A period of a string is a prefix of the string which being repeated forms the original string. The last repetition can be partial.
For example the shortest period of the string acbacbac
is acb
.
Your task is to find the shortest period in the string.
Input
The first and only line of the input contains a string with n characters.
Output
Output a single line with the shortest period in the given string.
Limits
- 1 \le n \le 10^6
- Each word consists of only English lower case letters a-z.
Example
Input:
acbacbac
Output:
acb