字母手环 (string)

题目描述

小 C 得到了一个手环，上面写着一圈的小写字母，总共有 $n$ 个字母。小 C 可以从任意起点开始，按照字母原有顺序读取这 $n$ 个字母，将它们拼成一个长为 $n$ 的字符串。

设一个长为 $n$ 的字符串从左到右第 $i$ 个字母为 $c_{i}$。定义一个长为 $n$ 的字符串的权值为 $\red{ \sum_{i=1}^{n} 66^{n-i} k_{i} }$ 其中 $k_{i}$ 表示 $c_{i}$ 是小写字母中的第几个，例如 a 是第一个，h 是第八个。

小 C 想要知道，从哪个起点开始，读出来的这个字符串权值最小。

输入格式

在文件 string.in 中读入。 仅一行，包含一个仅含小写字母的字符串，表示小 C 从手环上某一个起点读完 $n$ 个字母得到的字符串。

输出格式

在文件 string.out 中输出。 仅一行，包含一个 $n$ 个小写字母组成的字符串，即小 C 可以读到的权值最小的字符串。

样例

输入数据1

mnktm

输出数据1

ktmmn

输入数据2

abacacaabbcbaccabbab

输出数据2

aabbcbaccabbababacac

提示

数据范围与提示 对于全部数据，$2 \le n \le 5000$。共20个测试点，每个测试点分值相等，各档限制如下：