题目描述

给定字符串$S$，求与$S$循环同构的所有字符串中字典序最小的字符串。

循环同构：当$S$中可以选定一个位置$i$满足$S[i…n]+S[1…i-1]=T$，则称$S$与$T$循环同构。

输入格式

输入一行一个字符串$S$。

输出格式

输出一行一个字符串，表示你的答案。

样例输入 #1

CBBA

样例输出 #1

ACBB

说明/提示

有$1\leq |S|\leq 10^6$。