题目描述

你受雇潜入一个守口如瓶的组织——ACM ICPC区域评委团队，以获取利益。通过PC2“提交”软件，你知道可通过评委的登录名访问机密信息。但你不确定某个评委是否拥有所有相关信息，因此需要多个登录名。你得到了一份用户名列表，每个用户名对应的密码可按以下规则推导：

输入格式

输入仅包含大写字母（表示用户名）和回车符。每行（即每个用户名）长度不超过20字符，且需要潜入的“评委”不超过12个。奇怪的是，所有用户名中的字母均不重复。

输出格式

对每个用户名，输出一行长度不超过20的密码。密码由该用户名的21个按字典序连续的排列决定，其中第11个（中间位置）是用户名本身。例如，用户名为WORDFISH时，其字典序排列中包含以下连续序列（节选）：

..., WOISHRFD, WOISRDFH, WOISRDHF, WOISRFDH, WOISRFHD, WOISRHDF, WOISRHFD, WORDFHIS, WORDFHSI, WORDFIHS, WORDFISH, WORDFSHI, WORDFSIH, WORDHFIS, WORDHFSI, WORDHIFS, WORDHISF, WORDHSFI, WORDHSIF, WORDIFHS, WORDIFSH, ...

密码规则为：在这21个连续排列中，找到相邻字母的最小绝对距离最大的排列（若有多个排列具有相同的最大最小距离，则取字典序最小的那个），然后将该排列与最小距离拼接作为密码。例如，用户名为WORDFISH时，密码为WORDHSFI3。

输入数据示例 1

WORDFISH  

输出数据示例 1

WORDHSFI3  

来源

马尼拉 2006