题目描述

小红正在学习 KMP 算法，KMP 算法是用于计算一个字符串的循环节的算法，例如"abcabc”的循环节就是“abc"，"aba"的循环节是"aba”。 小红有一个字符串s，她想重排这个字符串，使得字符串循环节的长度最短，请输出重排后的字符串。

输入描述

第一行输入一个长度不超$10^5$的只由小写字母构成的字符串 8。

输出描述

输出一个字符串表示重排方案，如果存在多种重排方案，则输出字典序最小的那一个

样例

输入

cabbac

输出

abcabc

说明

"abc"是长度最短的循环节之一，且可以证明"abcabc"是字典序最小的重排方案。