Description

A string formed by concatenating several identical words end to end is defined as a compound word, and the words that make up this string are called the root. You need to determine whether the given string is a compound word. If it is, you need to find the root that appears first in it. If there are multiple possible roots, output the one with the shortest length. If it is not a compound word, output -1.

Note: If two strings can become exactly the same after rearranging the order of letters, they are considered the same word.

Input Format

One line containing a string of lowercase letters.

Output Format

If the given string is not a compound word, output -1.

Otherwise, output the shortest root that appears first.

aaaa

a

ab 

-1

bbabab

bba

Hint

Sample Explanation

Sample $1$

Notice that aa is also a root that appears first, but a is the shortest.

Sample $2$

This string consists of only one word ab, so it is not a compound word.

Sample $3$

The string is made up of two identical words bba and bab, and the one that appears first is bba.

Constraints

For $100\%$ of the testdata, the length of the string does not exceed $10^5$.

Notes

This problem is translated from COCI2015-2016 CONTEST #5 T2 MULTIGRAM.

Translated by ChatGPT 5