Pero is a passionate lover of riddles. The newest type of riddles he has come across requires the solver to check whether the given word is a multigram.

A multigram is a word that consists of concatenating two or more words that are all mutually anagrams. The first of these words is called the root of the multigram. For instance, the word bbabab is a multigram with the root bba because it consists of anagrams bba and bab.

Help Pero solve the riddle by determining whether his word is a multigram and determining its root in case it is. If there are multiple possible roots of the multigram, output the shortest.

Note: Two words are mutually anagrams if one of them can be obtained from the other by changing the letter order.


The first and only line of input contains a word of length at most $100\, 000$ lowercase English characters.


If the given word is not a multigram, output -1. Otherwise, output the shortest root of the given word in one line.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
Sample Input 3 Sample Output 3
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 2.7easy
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in