题目描述

给定一个非空字符串，"左移"操作将第一个字符移到字符串末尾，"右移"操作将最后一个字符移到字符串开头。例如，对"abcde"进行一次左移得到"bcdea"，对"abcde"进行两次右移得到"deabc"。给你一个由小写英文字母组成的非空字符串$S$。在对$S$进行零次或多次左移和右移操作后，找出可以得到的字典序最小的字符串和字典序最大的字符串。

输入格式

输入$S$。

输出格式

输出两行。第一行应包含$S_{min}$，第二行应包含$S_{max}$。
这里，$S_{min}$和$S_{max}$分别是通过对$S$进行零次或多次左移和右移操作后得到的字典序最小和最大的字符串。

样例

aaba

aaab
baaa

z

z
z

abracadabra

aabracadabr
racadabraab

样例解释

【样例1说明】
通过移位操作，我们可以得到四个字符串：aaab、aaba、abaa、baaa。其中字典序最小和最大的分别是aaab和baaa。
【样例2说明】
任何操作序列都会得到z。

数据范围

$S$由小写英文字母组成, $1\le |S| \le 1000$。

来源

• AtCoder ABC223B