Migrated from Lutece 3053 Necklace

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

商店里有很多条项链，项链由宝石组成。宝石一共有 $26$ 种，分别用小写字母 a ~ z 来表示。我们用一个只含小写字母的字符串来表示一条项链。

我们定义：两个字符串所表示的项链一致，当且仅当这两个字符串循环同构。两个长度为 $n$ 的字符串 $S$ 和 $T$ 循环同构，当且仅当存在至少一个位置 $i$，满足 $S_{i\ldots n}+S_{1\dots i-1}=T$。

现在给出一个字符串 $S$，你需要找出一个字符串 $T$，使得 $T$ 与 $S$ 所表示的项链一致，且 $T$ 的字典序最小。

Input

一个字符串 $S$。

Output

一行一个字符串 $T$，表示字典序最小的字符串。

Samples

bdbcaacdcd

aacdcdbdbc

Constraints

$|S| \leq 10^7$

Resources

2023 UESTC ICPC Training for String