Lexicographically Smallest String

You are given a non-empty string S of length n. Your task is to obtain the lexicographically smallest string by moving exactly one non-empty contiguous substring from its original position to the beginning of the string.

More formally, let \(S\) be a string of length \(n\) with indices \(0,1,\dots,n-1\). For each index \(i\) with \(1 \le i < n\), form a candidate string by taking the substring \(S[i:n]\) and concatenating it with \(S[0:i]\), i.e., the candidate is \(S[i:n] + S[0:i]\). Your task is to choose the candidate string that is lexicographically smallest among all possibilities.

Note that you must perform exactly one move, and the moved substring must be non-empty.

inputFormat

The input consists of a single line containing the string S.

\(1 \leq |S| \leq 10^6\)

outputFormat

Output a single line: the lexicographically smallest string obtainable by performing the allowed move.

programming

ammingprogr