Lexicographically Smallest Rotation

Given a string \( s \), your task is to determine the lexicographically smallest rotation of \( s \). A rotation by \( k \) positions is defined as \( s[k:] + s[:k] \), where \( 0 \leq k < n \) and \( n \) is the length of \( s \). Formally, you are to find:

\( \min_{0 \leq k < n}\{s[k:] + s[:k]\} \)

The input string contains only lowercase English letters.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing the string \( s \). \( s \) is non-empty and its length can be up to 100000 characters. It contains only lowercase English letters.

outputFormat

Output the lexicographically smallest rotation of \( s \) on standard output (stdout).

cabbage

abbagec