Contest Duration: - (local time) (100 minutes) Back to Home
B - String Shifting /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1. S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_iT_i が一致するか調べます。
2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_jT_j を比較して、S_jT_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
3. S_i \neq T_i である i が存在しない場合、ST の長さを比較して、ST より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

### 制約

• S は英小文字からなる。
• S の長さは 1 以上 1000 以下である。

### 入力

S


### 出力

2 行にわたって出力せよ。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれ S_{\min}, S_{\max} とおいたとき、1 行目には S_{\min} を、2 行目には S_{\max} を出力せよ。

### 入力例 1

aaba


### 出力例 1

aaab
baaa


### 入力例 2

z


### 出力例 2

z
z


どのように操作を行っても、得られる文字列は z のみです。

### 入力例 3

abracadabra


### 出力例 3

aabracadabr


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.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

1. Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
3. If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

### 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.

### Sample Input 1

aaba


### Sample Output 1

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.

### Sample Input 2

z


### Sample Output 2

z
z


Any sequence of operations results in z.

### Sample Input 3

abracadabra


### Sample Output 3

aabracadabr