### 问题描述 卓儿要考虑以下字符串转换： 1. 将字符 `#` 附加到字符串（我们假设 `#` 在字符串的所有其他字符中按字典顺序较小）。 2. 生成字符串的所有旋转。 3. 按递增顺序对旋转进行排序。 4. 根据这个顺序构造一个新字符串，其中包含每个旋转的最后一个字符。 例如，字符串 `babc` 变成 `babc#`。然后，旋转排序列表是 `#babc`，`abc#b`，`babc#`，`bc#ba` 和 `c#bab`。这产生了一个字符串 `cb#ab`。 ### 输入格式 唯一的输入行包含长度为 $n+1$ 的转换字符串。原始字符串的每个字符都是 $a-z$ 中的一个。 ### 输出格式 输出长度为 $n$ 的原始字符串。 ### 样例输入 ``` cb#ab ``` ### 样例输出 ``` babc ``` ### 评测数据规模 $1 \leq n \leq 10^5$。