单点时限: 2.0 sec
内存限制: 512 MB
Rachel得到了一个环形的字符串，但她很好奇，想要知道字典序最小的读法和最大的读法分别是什么。
她随便选了一个位置，将整个字符串环读给了你听。你需要告诉她字符串环的最小读法和最大读法。
本题中字典序的含义：在Rachel的这本字典中排的顺序，比如Rachel排在charming和gorgeous后面，但在silly和stupid前面。但特别的是，字符串中可能会出现大写和小写字母，其中大写字母排在小写字母前面但排在上一个小写字母后面。比如Bbc在bbc前面但在acc后面。
一行，一个字符串$S$。保证$S$的长度小于等于$1000$。
两行，两个字符串，分别表示最小的和最大的读法。
aAba
Abaa baaA
zZ
Zz zZ
abracadabra
aabracadabr racadabraab
On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.
For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.
You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.