Minimum Cyclic Cover 2 (Lexicographically Smallest)

Problem Description

You are given a string $a$, and you need to find the lexicographically smallest minimum cyclic cover of this string.

$b$ is the minimum cyclic cover of $a$ if and only if $a$ is a substring of the string obtained by concatenating multiple copies of $b$, and $b$ is the shortest string satisfying this condition. You need to find the lexicographically smallest minimum cyclic cover.

Given a string $a$, output a string: the lexicographically smallest minimum cyclic cover.

Input Format

One line containing a string $a$.

Output Format

Output one line containing a string: the answer.

Sample Input 1

bcabcabcabcab

Sample Output 1

abc

Sample Input 2

aaaaaaa

Sample Output 2

a

Constraints

For all data, $1 \leq |a| \leq 10^5$, and the string consists of lowercase letters only.