链接: https://cses.fi/problemset/task/1113

板块: String Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

考虑如下字符串变换：

1. 在字符串末尾追加字符 #（我们假设 # 在字典序上小于字符串中所有其他字符）
2. 生成该字符串的所有旋转
3. 按递增顺序对旋转进行排序
4. 根据该顺序，构造一个新字符串，包含每个旋转的最后一个字符

例如，字符串 babc 变为 babc#。然后，排序后的旋转列表为 #babc、abc#b、babc#、bc#ba 和 c#bab。由此得到字符串 cb#ab。

输入

唯一的一行输入包含长度为 $n+1$ 的变换后字符串。原始字符串的每个字符均为 a–z 中的一个。

输出

输出长度为 $n$ 的原始字符串。

数据范围

$1 \le n \le 10^6$

样例输入

cb#ab

样例输出

babc