ambigram

A sequence of characters is called an ambigram if it looks the same when we rotate the piece of paper it is written on 180 degrees around a perpendicular axis on its surface. Being given a sequence of characters we want to transform it into an ambigram, by modifying or deleting some letters.

The given sequence is written in capital English letters. We notice that:

• letters H, I, N, O, S, X and Z look unaltered after being rotated;
• letters M and W transform into one another after being rotated.

A few examples of ambigrams: MOW, XXXXXXXX, XMIWX, HXHXHXH.

We want to make the smallest possible number of modifications on the given sequence in order to produce an ambigram. Allowed modifications are:

• replacing a letter with another letter, an operation which costs the difference between the positions in the alphabet of the two letters. E.g. the cost of replacing letter F with letter H is 2 (F is the 6th letter of the alphabet and H is the 8th letter of the alphabet => cost=8-6=2); the cost of replacing letter I with letter F is 3=9-6;
• deleting a character from the given row, in which case the cost is equal to the shortest distance between the letter being deleted and a character that's outside the alphabet. In other words, deleting character ch from the given sequence has a cost of 1+min{dist(ch,'A'),dist(ch,'Z')}. E.g. deleting character C has cost 3 (=1+min(2,23)) and deleting character T has cost 7 (1+min(19,6)).

Input file ambigram.in contains on the first line the sequence for which the ambigram has to be determined.

The output file ambigram.out will contain on the first line a positive integer representing the minimum cost to transform the given word into an ambigram, and on the second line a sequence representing the ambigram obtained from the given sequence.

Constraints

• The given sequence will contain between 1 and 150 capital English letters.

ambigram.in	ambigram.out	Explanations
BXAJ	25 WM	delete B at cost 2 replace X with W at cost 1 delete A at cost 1 replace J with M at cost 3 Note: For the same cost we also get ambigram I (delete B, X and A and replace J with I), but the length of this sequence is smaller.