- Time limit: 1.00 s
- Memory limit: 512 MB
A period of a string is a prefix of the string which forms the original string when repeated. The last repetition can be partial.
Your task is to find the shortest period in the string.
Input
On the only line is a string with n characters from range a-z.
Output
Output the shortest period in the string.
Limits
- 1 \le n \le 10^5
Examples
Input:
acbacbac
Output:
acb
Input:
aa
Output:
a
Input:
az
Output:
az