yhx 的魔法手环 1585

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：11 AC：7 Score：100

Description

yhx 有一个魔法手环，手环上有 $n$ 颗珠子，每颗珠子上刻有一个小写字母，yhx 可以选择任意一个位置断开这个手环，使其成为一条珠串

对于一条长度为 $n$ 的珠串，从左往右每颗数字的的编号分别为 $1 \sim n$

若第 $i$ 个字母为 $a_i$ ，则这颗珠子的魔法值为 $66^{n-i} * number_i$，这里的 $number_i$ 表示的是 $a_i$ 是第几个小写字母

例如 $a_i = 'a'$，则 $number_i=1$，$a_i='b'$ 则 $number_i = 2$

现在 yhx 想知道，从什么位置断开这个魔法手环，可以使得断开后的珠串上所有珠子的魔法值之和最小？

Input

仅一行，包含一个仅含小写字母的字符串，表示 yhx 从手环上某个位置断开后得到的珠串

对于 $20\%$ 的数据：$2 \leq n \leq 10$ 。
对于 $40\%$ 的数据：$2 \leq n \leq 100$ 。
对于 $100\%$ 的数据：$2 \leq n \leq 5000$ 。
特殊的，存在 $20\%$ 的数据满足，仅存在 `abc` 三个字母

Output

仅一行，包含一个仅含小写字母的字符串，表示 yhx 从手环上某个位置断开后能得到的魔法值之和最小的珠串

Samples

input:

mnktm

output:

ktmmn