В непустой строке сдвиг влево перемещает первый символ в конец строки, а сдвиг вправо перемещает последний символ в начало строки. Например, сдвиг влево на строке
abcde приводит к
bcdea, а два сдвига вправо на
abcde приводят к
deabc.
Дана непустая строка
S, состоящая из строчных латинских букв. Среди строк, которые можно получить, выполнив ноль или более сдвигов влево и ноль или более сдвигов вправо, найдите лексикографически наименьшую строку и лексикографически наибольшую строку.
Входные данные
На вход подается одна строка
S.
S состоит из строчных английских букв. 1 <= |S| <= 1000, где
|S| - длина строки
S.
Выходные данные
Выведите в первой строке лексикографически наименьшу строку, во второй - лексикографически наибольшую строку.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
aaba |
aaab
baaa |
| 2 |
z |
z
z |
| 3 |
abracadabra |
aabracadabr
racadabraab |