436. The Diputs notation

time limit per test: 0.5 sec.
memory limit per test: 262144 KB
input: standard
output: standard



The Diputs notation is a notation to represent non-negative integer numbers. Diputs notation has 9 digits, starting with the least significant:

_.,-~='^

There can be a limited quantity of each digit character in the number representation:

Order of digitCharacterASCII codeMax. quantity
1_952
2.463
3,445
4-457
5~12611
6=6113
7'3917
8^9419
9"3423

A number representation in Diputs notation starts with the most significant digit, e.g.:

"""^^~~-,..__

Let us write down all possible number representations in Diputs notation and arrange them in the following order. Number A goes after number B if the representation of A in Diputs notation has more `"` (most significant digit) characters than the representation of B. If the numbers A and B have equal number of `"` characters, we then compare the number of '^' characters, and so on. Then we number this sequence, starting from 1 - and the result is the map which defines how numbers are represented in Diputs notation. Zero is represented with the 'O' character (code 79).

Examples:

Decimal notationDiputs notation
0O
1_
2__
3.
4._
6..
20,..__
34836480"
36682648"^'=~-,._


There is an input containing numbers in decimal notation, numbers in Diputs notation, and some other text. You must output the same numbers, but in another notation: the numbers in decimal notation should be converted to Diputs notation, and the numbers in Diputs notation should be converted to decimals. All numbers in the input are non-negative and do not exceed maximum number representable in Diputs notation. It is possible that the numbers will not be separated by space or other characters. You should parse the numbers in greedy way: when reading a number, you should take maximum number of characters that can form a decimal or Diputs representation of a number. For example, if you have three underscore characters ("___"), you should parse it as numbers "__" (2) and "_" (1) in Diputs notation. In this case, the resulting string will be "21". When parsing decimal numbers, your program should work the same way. There should be no leading zeros in decimal numbers. For example, you should parse the string "020" as decimal numbers 0 and 20, and the result will be "O,..__". If you would get a decimal number larger than the maximum number representable in Diputs notation, you should split it into two or more decimal numbers in greedy way, as described.

Some examples:

InputOutput
___21
020O,..__
_121,


Because we feel that your task is too easy, you should sort the numbers in ascending order, if the total number of numbers in the input is odd. Only numbers should be reordered; the notation of a number in a certain location should not be changed. For example, for input "2 O _" you should first recognize the notation (decimal, diputs, diputs), then convert it to "__ 0 1", inverting the notation (it is now diputs, decimal, decimal), and then sort the numbers while preserving the notation. Thus, the sorted array is 0, 1 and 2, the notations are (diputs, decimal, decimal), so the answer should be "O 1 2". Take a look at the sample input for better understanding.

Size of input and output will not exceed 1 megabyte (106 bytes).

Sample test(s)

Input
Test #1:

need 2 sort
O
_

Test #2:

1
2
020
___
-A-
,._
0

Output
Test #1:

need O sort
1
2

Test #2:

_
__
O,..__
21
72A72
16
O

Author:
Resource:Izhevsk State Technical University Contest 3
Date:February 06, 2009