Minimal Shift
(Time limit: 1 sec. Memory limit: 16 MB Difficulty: 61%)
A cyclic shift of the string s is the string sk+1sk+2…sns1s2…sk for some k (0 ≤ k < n) where n is the length of the string s.
For a given string, find out its lexicographically minimal shift, i.e., among all possible cyclic shifts of the string find one that is the first in alphabetical order.
Input
The only line of input contains a string consisting of characters with ASCII codes 33 to 127. A string length can be up to 105.
Output
Output one line - the minimal lexicographic shift of the input string.
Samples
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | program | amprogr |
| 2 | cab | abc |
| 3 | bbbbb | bbbbb |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 