#CS1113. 字符串变换

字符串变换

题目背景

翻译自 CSES-13 题。

题目描述

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

• 在字符串末尾追加字符 #（假设 # 在字典序上小于所有其他字符）。

• 生成该字符串的所有旋转。

• 将这些旋转按字典序升序排列。

• 根据这个顺序，构建一个新的字符串，其中包含每个旋转的最后一个字符。

例如，字符串 babc 变换后变为 babc#。然后，旋转后的字符串列表是：#babc, abc#b, babc#, bc#ba, 和 c#bab。按字典序排序后，得到的字符串是 cb#ab。

输入格式

唯一的一行输入包含变换后的字符串，长度为 n+1n+1n+1，其中原始字符串中的每个字符都是小写字母 a 到 z。

输出格式

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

样例

cb#ab

babc

说明/提示

1≤n≤106。