[ABC223B] String Shifting
配点 : 点
問題文
空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。
例えば、abcde に対して左シフトを 回行うと bcdea となり、右シフトを 回行うと deabc となります。
英小文字からなる空でない文字列 が与えられます。 に対し左シフトと右シフトをそれぞれ好きな回数（ 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 の大小を判定するアルゴリズムを以下に説明します。
以下では「 の 文字目の文字」を のように表します。また、 が より辞書順で小さい場合は 、大きい場合は と表します。
- のうち長さが大きくない方の文字列の長さを とします。 に対して と が一致するか調べます。
- である が存在する場合、そのような のうち最小のものを とします。そして、 と を比較して、 が よりアルファベット順で小さい場合は 、そうでない場合は と決定して、アルゴリズムを終了します。
- である が存在しない場合、 と の長さを比較して、 が より短い場合は 、長い場合は と決定して、アルゴリズムを終了します。
制約
- は英小文字からなる。
- の長さは 以上 以下である。
入力
入力は以下の形式で標準入力から与えられる。
出力
行にわたって出力せよ。 に対し左シフトと右シフトをそれぞれ好きな回数（ 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれ とおいたとき、 行目には を、 行目には を出力せよ。
aaba
aaab
baaa
操作によって、aaab aaba abaa baaa の 通りの文字列を得ることができます。
これらのうち辞書順で最小、最大のものはそれぞれ aaab baaa です。
z
z
z
どのように操作を行っても、得られる文字列は z のみです。
abracadabra
aabracadabr
racadabraab