题目背景

小明在一家纪念品工作室里设计文字印章。客户提出了一个特别的要求：印章盖出的文字在纸张旋转 $180^\circ$ 后，仍然要与原来完全相同。

工作室使用的字体中，只有部分大写字母在旋转后仍然可以辨认。小明已经收到一个原始单词，他可以修改或删除其中的字母，并希望用尽可能小的代价把它变成符合要求的翻转文字。

题目描述

一个翻转文字是一个非空字符串：将写有该字符串的纸张旋转 $180^\circ$ 后，看到的字符串仍与原字符串完全相同。

本题只考虑大写英文字母。在所使用的字体中：

• H、I、N、O、S、X、Z 旋转 $180^\circ$ 后保持不变；
• M 旋转后变成 W；
• W 旋转后变成 M；
• 其余字母旋转后都不能作为翻转文字中的字符。

因此，判断一个字符串是否为翻转文字时，需要先将字符串反转，再把每个字符按照上述规则旋转。若得到的字符串与原字符串相同，则它是翻转文字。

例如，MOW、XXXXXXXXXXX、XMIWX、HXHXHXHXHXH 都是翻转文字。空串不是翻转文字。

给定一个原始字符串 $s$，你可以进行以下操作：

修改字符

将一个字母修改为另一个字母，代价等于它们在英文字母表中的距离。

例如：

• 将 F 修改为 H，代价为 $2$；
• 将 I 修改为 F，代价为 $3$。

字母表不视为首尾相连，例如将 A 修改为 Z 的代价是 $25$，而不是 $1$。

删除字符

可以不断把一个字母修改为字母表中相邻的字母，直到它从 A 的左侧或 Z 的右侧移出字母表，此时该字母被删除。删除后，它左右两侧剩余的字符会自动拼接起来。

删除一个字母时，可以选择从字母表的任意一端移出，并取代价较小的方案。例如：

• C → B → A → 移出字母表，代价为 $3$；
• T → U → V → W → X → Y → Z → 移出字母表，代价为 $7$。

你需要通过修改或删除字符，将 $s$ 变成一个非空的翻转文字 $t$。

选择答案时依次遵循以下规则：

1. 总操作代价尽可能小；
2. 在总代价相同的方案中，$t$ 的长度尽可能大；
3. 如果代价和长度都相同，选择字典序最小的 $t$。

请输出最终得到的字符串 $t$。

输入格式

输入一行，包含一个仅由大写英文字母组成的字符串 $s$。

输出格式

输出一行，包含按照上述规则得到的最优翻转文字 $t$。

数据范围

• $1 \le |s| \le 50$；
• $s$ 中的每个字符都是大写英文字母 A～Z。

样例

样例 1

BXC

X

删除 B 的代价为 $2$，删除 C 的代价为 $3$，保留 X 不需要代价，因此总代价为 $5$。

注意，BXB 不是翻转文字。

样例 2

XIXHZMOAOSHXIX

XIXHMOOWHXIX

可以删除 A 和 Z，并将 S 修改为 W，总代价为 $1+1+4=6$。

样例 3

C

H

删除 C 的代价为 $3$，但结果会是空串，而空串不是翻转文字。将 C 修改为 H 的代价为 $5$。

样例 4

AMWZ

MW

字母表不首尾相连，因此不能以很小的代价把 A 修改为 Z。虽然 ZMWZ 比 MW 更长，但构造它需要 $25$ 的代价。

样例 5

ABCDEFGHIJKLMNOP

HHHHIIIIHHHH

样例 6

MIW

MIW

样例 7

MWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMW

MWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMW

样例 8

MWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWM

NMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWN

样例 9

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

H

样例 10

DDDDDDDDDD

HHHHHHHHHH

样例 11

FDKLKJSDKJSAKJDASDLKDLKHALKASKL

HHINHIWHIISIISIIHMIHNIHH

样例 12

GLSMSMWMSIDHSFLLSMDMMWMWLSFKDFH

HISNWNWNSIHHSHHISNMNMNSIH

样例 13

HEREISASTRINGOFMODESTLENGTH

HHNHISSONHNHNHNOSSIHNHH

样例 14

WHOKNOWSWHATTHISMIGHTBE

HMHHIWSWHSSHMSMIHHWH

样例 15

LLLLLSTUVW

MMMMMWWWWW

样例 16

ZZZZZZZZZZZZ

ZZZZZZZZZZZZ

样例 17

ZZYZZZZZZZZZZ

ZZZZZZZZZZZZZ

样例 18

Y

X

样例 19

ZZZZZZYZZZZZZ

ZZZZZZXZZZZZZ

样例 20

DDDDDDDDDDD

HHHHHHHHHHH