Smallest Cyclic Shift

You are given a binary string S consisting only of characters '0' and '1'. Your task is to find the lexicographically smallest string among all possible cyclic shifts of S.

More formally, if S has length n, let
\( S_i = S[i]S[(i+1)\,\%\,n] \dots S[(i+n-1)\,\%\,n] \) for \(0 \le i < n\).
Then, you need to output \( \min_{0 \le i < n} S_i \) in lexicographical order.

Note: A cyclic shift means that the string is rotated so that some prefix is moved to the end of the string.

inputFormat

The input consists of a single binary string S (composed only of '0' and '1') provided via standard input.

It is guaranteed that S is non-empty.

outputFormat

Print the lexicographically smallest string that can be obtained from any cyclic shift of S via standard output.

11001

00111