Root Word in Compound String

We define a compound word as a string formed by concatenating multiple copies of the same word. The word used in this concatenation is called the root. Note that two words are considered identical if their letters, when sorted in lexicographical order, are the same.

Given a string S, determine whether it is a compound word. If it is, find the first occurrence of the root word (i.e. the substring corresponding to the first group in the segmentation). If there are multiple possibilities, output the one with the shortest length. Otherwise, output -1.

In more formal terms, a string \(S\) of length \(n\) is a compound word if there exists an integer \(d\) with \(1 \le d 1\) (where \(k = n/d\)) such that

[ \text{sort}(S[0:d]) = \text{sort}(S[i\cdot d:(i+1)\cdot d]) \quad \text{for every } i = 1, 2, \ldots, k-1, ]

where \(\text{sort}(\cdot)\) denotes the transformation that sorts the characters of the string in lexicographical order. The substring \(S[0:d]\) is then considered the root word. Otherwise, the answer is -1.

inputFormat

The input consists of a single line containing the non-empty string S.

outputFormat

Output the first occurrence of the root word if S is a compound word under the described condition; otherwise, output -1.

sample

abcabc

abc