Secret — MAX#2560
Agent Smith transfers secret information to a secret center, consisting of a single strictly positive integer. To encode the number, he replaces each digit with its corresponding word and concatenates the words. For example, can be encoded as . Agent Smith knows four languages (the st, nd, rd, and th). In these languages, the digits from to are written as follows (all letters are uppercase Latin letters with ASCII codes in the range –):
After encoding, Smith adds some "noise" to the code—additional uppercase Latin letters. Any letters (including those already used in the code) may be added in any quantity and at any position in the code.
Write a program that reads such a code and finds the largest possible number that could be coded by the given string, under two different assumptions:
We do not know which language Smith used, but it was the same language (from the list) throughout the whole code;
Smith could have used different languages (from the list) for different digits, or the same language for all digits.
Your program should read all input lines and process them separately. Each line consists of at most 10^5 uppercase Latin letters composing the code. The total size of input is less than MB.
For each input line, output two integers separated by a single space—the largest numbers according to the above two assumptions, respectively.
It is guaranteed that each code was constructed from a valid positive (non-zero) integer. Therefore, both results will always be positive. Your program should output them without leading zeroes.
Esempio 1