字符串移位

题目描述

对一个非空字符串，一次左移将其第一个字符移到字符串末尾，一次右移将其最后一个字符移到字符串开头。

例如，对 abcde 进行一次左移得到 bcdea，对 abcde 进行两次右移得到 deabc。

给定一个由小写英文字母构成的非空字符串 $S$。在通过对 $S$ 进行零次或多次左移以及零次或多次右移所能得到的字符串中，找出字典序最小的字符串和字典序最大的字符串。

什么是字典序？

简单来说，字典序就是单词在词典中排列的顺序。作为更正式的定义，下面给出确定两个不同字符串 $S$ 和 $T$ 的字典序大小的算法。

下面，用 $S_i$ 表示 $S$ 的第 $i$ 个字符。另外，如果 $S$ 在字典序上小于 $T$，记作 $S \lt T$；如果 $S$ 在字典序上大于 $T$，记作 $S \gt T$。

设 $L$ 为 $S$ 和 $T$ 中较小的长度。对每个 $i=1,2,\dots,L$，检查 $S_i$ 和 $T_i$ 是否相同。

如果存在 $i$ 使得 $S_i \neq T_i$，设 $j$ 为最小的这样的 $i$。然后比较 $S_j$ 和 $T_j$：如果 $S_j$ 在字母顺序上比 $T_j$ 靠前，则判定 $S \lt T$ 并结束；如果 $S_j$ 比 $T_j$ 靠后，则判定 $S \gt T$ 并结束。

如果不存在 $i$ 使得 $S_i \neq T_i$，则比较 $S$ 和 $T$ 的长度：如果 $S$ 比 $T$ 短，则判定 $S \lt T$ 并结束；如果 $S$ 比 $T$ 长，则判定 $S \gt T$ 并结束。

输入格式

输入按以下格式从标准输入给出：

$S$

输出格式

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

样例

aaba

aaab
baaa

通过移位可以得到四个字符串：aaab、aaba、abaa、baaa。其中字典序最小和最大的分别是 aaab 和 baaa。

z

z
z

任何操作序列都会得到 z。

abracadabra

aabracadabr
racadabraab

数据范围

• $S$ 由小写英文字母构成。
• $S$ 的长度在 $1$ 到 $1000$（含）之间。