E. Messenger
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a double-launch problem.

The IT company "Crutches and Bicycles" has developed a new text messenger that allows users to exchange messages in the form of strings composed of uppercase Latin letters with a length of no more than 1000 characters.

Unfortunately, there is a bug in the code: when transmitting a message, one of the letters may unexpectedly be replaced by some other letter. The developers cannot find the bug in the code, so they decided to implement a "crutch": to encode messages in such a way that they can be uniquely restored under the condition that no more than one letter has been corrupted. At the same time, the developers want the encoded string to also consist only of uppercase Latin letters, and its length should exceed the length of the original string by no more than 10 characters.

Develop a method for encoding and decoding that meets these requirements.

Input

The first line of the input contains a number $$$t$$$, equal to 1 or 2.

If $$$t=1$$$, then the second line of input contains the message that needs to be encoded. It consists of uppercase Latin letters and has a length of 1 to 1000 characters.

If $$$t=2$$$, then the second line of input contains a previously encoded message by your program that needs to be decoded. No more than one character in this string may have been replaced by any uppercase Latin letter.

Output

Output a single string of uppercase Latin letters — the encoded or decoded message.

Example
Input
1
ABC
Output
AAABBBCCC
Input
2
AXABBBCCC
Output
ABC