Lexicographically Smallest Cyclic Shift

You are given a non-empty string S. A cyclic shift of a string is obtained by moving some (possibly zero) characters from the beginning of the string to its end. For example, the string ABC has cyclic shifts ABC, BCA, and CAB.

Your task is to determine the lexicographically smallest string that can be obtained by any cyclic shift of S.

The lexicographical order is defined in the usual way over the alphabet. Formally, if you denote by S_i the cyclic shift starting at index i, then you need to find the minimum among { S₀, S₁, ..., S_n-1 }.

Mathematically, if S = s_0 s_1 ... s_{n-1}, then the cyclic shift starting at index i is given by: \[ S_i = s_i s_{i+1} \ldots s_{n-1} s_0 s_1 \ldots s_{i-1} \] and you need to output
\(\min_{0 \leq i < n} S_i\).

inputFormat

The input consists of a single line containing a non-empty string S composed of uppercase English letters. It is guaranteed that 1 \( \leq |S| \leq 10^5 \).

outputFormat

Output a single line which is the lexicographically smallest cyclic shift of the given string.

ABCD

ABCD