Multigram

Interview

Time limit1sMemory limit64 MB

Summary

Decide whether the word splits into two or more equal anagram blocks and print the shortest such block, or -1.

Level: Medium4 of 10
Topics: String, Hash map
Solved: No attempts yet

Problem

Pero likes riddles. The newest riddle he has met asks whether a given word is a multigram.

A multigram is a word built by concatenating two or more words that are anagrams of one another. The first of those words is the root of the multigram. For example, bbabab is the concatenation of bba and bab, which are anagrams, so bbabab is a multigram with root bba.

Decide whether the given word is a multigram, and if it is, find its root. If several words can be the root, print the shortest one.

Two words are anagrams of each other when one can be obtained from the other by reordering its letters.

Input

The first line contains a word made of lowercase English letters. The length of the word is at most $100\,000$ .

Output

If the given word is not a multigram, print -1.

Otherwise print the shortest root on one line.

Hint

For the word aaaa the word aa is also a root, but a is shorter. The word ab is not a multigram because a and b are not anagrams.

Examples3

Example 1
Input
```
aaaa
```
Expected output
```
a
```
Example 2
Input
```
ab
```
Expected output
```
-1
```
Example 3
Input
```
bbabab
```
Expected output
```
bba
```