На непорожньому рядку зсув вліво переміщує перший символ до кінця рядка, а зсув вправо переміщує останній символ на початок рядка.

Наприклад, зсув ліворуч на 'abcde' призводить до 'bcdea', а два зсуви вправо на 'abcde' призводять до 'deabc'.

Вам надається не порожній рядок \(S\), що складається з малих англійських літер. Серед рядків, які можна отримати, виконуючи нуль або більше зсувів ліворуч і нуль або більше праворуч на \(S\), знайдіть лексикографічно найменший рядок і лексикографічно найбільший рядок. (Тобто рядокякий буде в словнику йти перший, і який останній, зі всіх можливих отриманих рядків).

Формат вхідних даних

Вхідний потік містить рядок \(S\) (\(1 \le |S| \le 1000\)), який містить лише символи проміжку ['a'..'z'].

Формат вихідних даних

У вихідний потік виведіть два рядки. Перший рядок повинен містити \(S_{\min}\), а другий рядок повинен містити \(S_{\max}\).

Тут \(S_{\min}\) і \(S_{\max}\) відповідно лексикографічно найменший і найбільший рядки, отримані шляхом виконання нуля або більше зсувів ліворуч і нуля або більше праворуч на \(S\).

Примітка

До прикладу 1:

Виконуючи зсуви, ми можемо отримати чотири рядки: 'aaab', 'aaba', 'abaa', 'baaa'. Лексикографічно найменшими і найбільшими серед них є відповідно 'aaab' і 'baaa'.

Приклад вхідних даних

aaba

Приклад вихідних даних

aaab
baaa

Приклад вхідних даних

z

Приклад вихідних даних

z
z

Приклад вхідних даних

abracadabra

Приклад вихідних даних

aabracadabr
racadabraab