题目背景

翻译自 CSES-1113 题。

题目描述

考虑以下字符串变换过程：

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^{6}$。