题目描述

有一种英文字谜游戏，一开始创作者选一个称为 "根" 的单词 R ，然后可能多次打乱 R，连接到 R 单词后面。例如：bbabababb，是根单词 bba，与乱序单词 bab、abb 连接组成。

字谜参加者要面对一个字符串，找出最短的 "根" 单词。如果找不到输出 -1 。

解题提示

“根” 是分多次打乱之后连接到 R 单词的后面，并非是多个根连在一起然后打乱再连接到单词 R 后面。这个细节很重要，意味着，整个单词可以按照“根”的长度分成很多段，每一段内包含的字母是一样的。

输入格式

1 行：长度不超过 100,000 的小写英文字母组成的字符串。

输出格式

最短的根单词（是输入字符串的前缀）。如果找不到根单词，输出 -1 。

样例

aaaa

a

ab

-1

bbabab

bba