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