Mrs. White-Cloud is a music teacher in a high school. She loathes being called "White Cloud" by her students drastically. Once she hears anybody saying "White Cloud", Mrs. White-Cloud always comes to exceedingly furious and ridiculous. Since Mrs. White-Cloud is so skeptical, the students try to avoid mentioning the ``She-Who-Must-Not-Be-Named" keyword cautiously. They developed a method: to encode words by circular shifting the word to the lexicographically smallest one. Please help them to encode their words.
The lexicographical order is a binray relation of two strings to compare the first non-identical character if both strings are not prefix to the other, otherwise compare their lengths. For instance, "qaz" \(<\) "qwerty".
The circular shift of a string \(s\) could be deem as append a substring starting from the front of \(s\) to the remaing of \(s\). For instance, "qaz", "azq" and "zqa" are all circular shifts of each one.
There is a string \(s\) containing only lower case English letters, where \(|s| < 5000\).
Please print out the lexicographically smallest string among all circular shift of \(s\). Remember to put a newline character at the end of line.