String Shifting

题目描述

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.

输入格式

Input is given from Standard Input in the following format: $S$

输出格式

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

z

z
z

abracadabra

aabracadabr
racadabraab

提示

$S$ consists of lowercase English letters. The length of $S$ is between $1$ and $1000$ (inclusive).By performing shifts, we can obtain four strings: $aaab$, $aaba$, $abaa$, $baaa$. The lexicographically smallest and largest among them are $aaab$ and $baaa$, respectively.
Any sequence of operations results in $z$.

标签: AtCoder|abc223B

来源

AtCoder|abc223B