该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

考古队在发掘一座神秘古墓时，发现了上百把青铜机关锁。每把锁的核心部件是一个刻有字母的环形转环，转环上的字母按照顺时针方向依次排列成一个字符串。通过转动转环，字母序列会产生循环位移——例如，对于字符串 kaogu，转动后可得到 aoguk、oguka 等不同的排列形式。

根据墓室壁画上的记载：只有当一个机关锁的转环上呈现的字母序列是所有可能转动结果中字典序最小的那个时，锁内部的精密齿轮才会咬合，机关锁才会开启。

由于机关锁数量众多，人工尝试显然来不及。作为考古队的技术支持，请你编写一个程序，快速计算出给定转环上字母排列后，能使机关锁开启的那个字典序最小的序列。

输入格式

单行输入一个仅由小写英文字母组成的字符串，表示机关锁转环上字母的初始排列（按顺时针方向，从某一固定位置开始读取）。

输出格式

输出一个字符串，表示能够开启机关锁的字典序最小的环形转动结果。

样例

样例 1

dcbabcd

abcddcb

样例解释：
转环上七个字母的所有轮转结果分别为：dcbabcd、cbabcdd、babcddc、abcddcb、bcddcba、cddcbab、ddcbabc。其中字典序最小的是 abcddcb，即机关锁开启时呈现的序列。

样例 2

bacbac

acbacb

样例解释：
该转环上的字母排列具有周期性，不同的轮转结果实际上只有三种：bacbac、acbacb、cbacba。按字典序比较后，最小的是 acbacb，因此该机关锁开启时显示的序列为 acbacb。

数据规模与约定

对于 $100\%$ 的数据，$1 \le \text{字符串长度} \le 10^6$。字符串中仅包含小写英文字母。