In 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 the string
abcde results in
bcdea, and two shifts to the right by
abcde results in
deabc.
Given a non-empty string
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, find the lexicographically smallest string and the lexicographically largest string.
Input
The input is a single string
S.
S consists of lowercase English letters. 1 <= |S| <= 1000, where
|S| is the length of the string
S.
Imprint
Print the lexicographically smallest string in the first line, and the lexicographically largest string in the second line.
Examples
| # |
Input |
Output |
| 1 |
aaba |
aaab
baaa |
| 2 |
z |
z
z |
| 3 |
abracadabra |
aabracadabr
racadabraab |