Smallest Lexicographical Rotation

Given a string s consisting of lowercase English letters, your task is to compute its smallest lexicographical rotation. A rotation of a string is obtained by moving a prefix of the string to its end. Formally, if s = s_0s_1\dots s_{n-1}, then the rotation starting at index i is defined as:

\( R_i = s_i s_{i+1} \dots s_{n-1} s_0 s_1 \dots s_{i-1} \)

You need to find the rotation which is lexicographically smallest among all n rotations.

For example, if s = "baca", its rotations are "baca", "acab", "caba", and "abac"; therefore, the smallest lexicographical rotation is "abac".

inputFormat

The input consists of a single line containing a non-empty string s (1 ≤ |s| ≤ 10⁴), composed only of lowercase English letters.

outputFormat

Output the smallest lexicographical rotation of the string s.

## sample

baca

abac

</p>