Problem Description

A string composed of multiple identical words concatenated end-to-end is defined as a multigram, and the word that forms this string is called the root word. You need to determine if it is a multigram. If it is, you need to find the first occurring root word with the shortest length. If it is not a multigram, output -1.

Note: If two strings can be identical after rearranging their letters, they are considered the same word.

Input Format

Input consists of a single line containing a string composed of lowercase letters.

Output Format

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

Otherwise, output the first occurring root word with the shortest length.

Sample Input and Output

Sample Input #1

aaaa

Sample Output #1

a

Sample Input #2

ab

Sample Output #2

-1

Sample Input #3

bbabab

Sample Output #3

bba

Notes

Sample Explanation

Sample 1

Note that aa is also the first occurring root word, but a is the shortest.

Sample 2

This string is composed of the word ab and is not a multigram.

Sample 3

The string is composed of two identical words bba and bab, with the first occurring word being bba.

Data Size and Constraints

For 100% of the data, the length of the string does not exceed \(10^5\).

Notes

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

见题面 Input 部分

见题面 Output 部分