最小循环覆盖2

题目描述

给你一个字符串 $a$，你需要求出这个字符串的字典序最小的最小循环覆盖。

$b$ 是 $a$ 的最小循环覆盖，当且仅当 $a$ 是通过 $b$ 复制多次并连接后得到的字符串的子串，且 $b$ 是满足条件的字符串中长度最小的。你需要找出字典序最小的最小循环覆盖。

输入一个字符串 $a$，输出一个字符串表示字典序最小的最小循环覆盖。

输入格式

一行一个字符串 $a$。

输出格式

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

样例输入 1

bcabcabcabcab

样例输出 1

abc

样例输入 2

aaaaaaa

样例输出 2

a

数据范围

对于所有数据，保证 $1\leq |a| \leq 10^5$，字符串均由小写字母构成。