Smallest Lexicographical Rotation

Given a non-empty string s, find the rotation of the string that is the smallest in lexicographical order.

A rotation of a string s is defined as taking some number of characters from the beginning of the string and appending them at the end in the same order. Formally, for a string s of length n, a rotation can be represented as:

\( s[i:] + s[:i] \) for any \( 0 \leq i < n \).

Your task is to output the lexicographically smallest rotation of the given string.

inputFormat

The input consists of a single line containing a non-empty string s of lowercase English letters.

For example:

bca

outputFormat

Output the lexicographically smallest rotation of the string s.

For example:

abc

## sample

bca

abc