Score : $200$ points

Problem Statement

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.

Constraints

• $S$ consists of lowercase English letters.
• The length of $S$ is between $1$ and $1000$ (inclusive).

Input

Input is given from Standard Input in the following format:

$S$

Output

Print two lines. The first line should contain $S_{\min}$, and the second line should contain $S_{\max}$. Here, $S_{\min}$ and $S_{\max}$ are respectively the lexicographically smallest and largest strings obtained by performing zero or more left shifts and zero or more right shifts on $S$.

aaba

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

z

z
z

Any sequence of operations results in z.

abracadabra

aabracadabr
racadabraab