<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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 digit	Character	ASCII code	Max. quantity
1	_	95	2
2	.	46	3
3	,	44	5
4	-	45	7
5	~	126	11
6	=	61	13
7	'	39	17
8	^	94	19
9	"	34	23

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 notation	Diputs notation
0	O
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:

Input	Output
___	21
020	O,..__
_12	1,


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

<|response|>
## 1. Abridged Problem Statement

Diputs notation represents non-negative integers using 9 digit characters, from least significant to most significant:

```text
_ . , - ~ = ' ^ "
```

Each character has a maximum allowed repetition count:

```text
_ : 2
. : 3
, : 5
- : 7
~ : 11
= : 13
' : 17
^ : 19
" : 23
```

Zero is represented by the character:

```text
O
```

The input is arbitrary text containing decimal numbers, Diputs numbers, and other characters.

You must:

- convert every decimal number to Diputs notation,
- convert every Diputs number to decimal notation,
- leave all other characters unchanged.

Numbers may appear without separators, so parsing must be greedy.

If the total number of recognized numbers is odd, sort the numeric values increasingly, while preserving the output notation type of each number position.

Input and output sizes are at most `10^6` bytes.

---

## 2. Key Observations

### Observation 1: Diputs is a mixed-radix numeral system

For each Diputs digit, the count can range from `0` to its maximum.

So the bases are:

```text
_ : 0..2   => base 3
. : 0..3   => base 4
, : 0..5   => base 6
- : 0..7   => base 8
~ : 0..11  => base 12
= : 0..13  => base 14
' : 0..17  => base 18
^ : 0..19  => base 20
" : 0..23  => base 24
```

Define:

```text
place[0] = 1
place[i + 1] = place[i] * (max_count[i] + 1)
```

Then the decimal value of a Diputs number is:

```text
value = count[0] * place[0]
      + count[1] * place[1]
      + ...
      + count[8] * place[8]
```

The maximum representable number is:

```text
place[9] - 1 = 836075519
```

---

### Observation 2: Decimal to Diputs conversion is digit extraction

For a decimal number `n`, the count of digit `i` is:

```text
count[i] = (n / place[i]) % (max_count[i] + 1)
```

Then print characters from most significant to least significant.

If `n == 0`, print `O`.

---

### Observation 3: Diputs to decimal conversion is summing place values

Each Diputs character contributes its place value.

For example:

```text
,..__
```

means:

```text
1 comma + 2 dots + 2 underscores
```

So:

```text
value = place[2] + 2 * place[1] + 2 * place[0]
```

---

### Observation 4: Greedy parsing

While scanning the input:

- If the current character is a decimal digit:
  - if it is `0`, parse exactly one character,
  - otherwise consume as many following digits as possible while the value stays `<= max_value`.

- If the current character is `O`, parse it as Diputs zero.

- If the current character is a Diputs digit:
  - consume the longest valid Diputs representation,
  - digit significance must be non-increasing from left to right,
  - no digit may exceed its maximum count.

- Otherwise, it is normal text.

---

### Observation 5: Sorting rule only changes values

If the total number of parsed numbers is odd:

- sort the numeric values,
- assign sorted values back to number positions in order,
- preserve the original notation type of each position.

For example:

```text
2 O _
```

Parsed as:

```text
decimal 2, Diputs 0, Diputs 1
```

After sorting values:

```text
0, 1, 2
```

The positions still output as:

```text
Diputs, decimal, decimal
```

So the answer is:

```text
O 1 2
```

---

## 3. Full Solution Approach

1. Read the entire input as a single string.

2. Precompute:
   - Diputs digit characters,
   - maximum counts,
   - mixed-radix place values,
   - maximum representable value,
   - lookup table from character to Diputs digit index.

3. Scan the input from left to right.

4. Whenever a number is found, store a token containing:
   - starting position,
   - original length,
   - numeric value,
   - whether it was originally decimal.

5. If the number of tokens is odd:
   - collect all token values,
   - sort them,
   - assign them back to tokens in order.

6. Build the output:
   - copy unchanged text between tokens,
   - for each token:
     - if it was decimal, output Diputs,
     - otherwise output decimal.

### Complexity

Let `N` be input length and `K` be the number of parsed numbers.

Tokenization is linear:

```text
O(N)
```

Sorting, only if needed:

```text
O(K log K)
```

Memory usage:

```text
O(N)
```

---

## 4. C++ Implementation with Detailed Comments

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Token {
    size_t start;       // Start position in the original input
    size_t length;      // Length of the original token
    long long value;    // Numeric value of the token
    bool wasDecimal;    // true if original token was decimal
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Read the whole input.
    stringstream buffer;
    buffer << cin.rdbuf();
    string text = buffer.str();

    // Diputs digits from least significant to most significant.
    const string digits = "_.,-~='^\"";

    // Maximum allowed counts for each digit.
    const int maxCount[9] = {
        2, 3, 5, 7, 11, 13, 17, 19, 23
    };

    // place[i] is the value of one occurrence of digit i.
    long long place[10];
    place[0] = 1;

    for (int i = 0; i < 9; i++) {
        place[i + 1] = place[i] * (maxCount[i] + 1);
    }

    // Maximum number representable in Diputs notation.
    long long maxValue = place[9] - 1;

    // Character to Diputs digit index.
    // -1 means the character is not a Diputs digit.
    array<int, 256> digitId;
    digitId.fill(-1);

    for (int i = 0; i < 9; i++) {
        digitId[(unsigned char)digits[i]] = i;
    }

    auto isDecimalDigit = [](unsigned char c) {
        return c >= '0' && c <= '9';
    };

    // Convert a valid Diputs substring text[l:r) to decimal.
    auto diputsToDecimal = [&](size_t l, size_t r) -> long long {
        long long value = 0;

        for (size_t i = l; i < r; i++) {
            int id = digitId[(unsigned char)text[i]];
            value += place[id];
        }

        return value;
    };

    // Convert a decimal number to Diputs notation.
    auto decimalToDiputs = [&](long long n) -> string {
        if (n == 0) {
            return "O";
        }

        int count[9];

        // Extract mixed-radix digits.
        for (int i = 0; i < 9; i++) {
            count[i] = (n / place[i]) % (maxCount[i] + 1);
        }

        string result;

        // Print from most significant to least significant.
        for (int i = 8; i >= 0; i--) {
            result.append(count[i], digits[i]);
        }

        return result;
    };

    vector<Token> tokens;

    size_t n = text.size();

    // Greedy scan of the whole input.
    for (size_t i = 0; i < n; ) {
        unsigned char c = text[i];

        // Case 1: decimal number.
        if (isDecimalDigit(c)) {
            size_t j = i;
            long long value = 0;

            // Decimal numbers cannot have leading zeroes.
            // Therefore '0' alone is one token.
            if (c == '0') {
                j = i + 1;
                value = 0;
            } else {
                // Consume as many digits as possible without exceeding maxValue.
                while (j < n && isDecimalDigit((unsigned char)text[j])) {
                    long long nextValue = value * 10 + (text[j] - '0');

                    if (nextValue > maxValue) {
                        break;
                    }

                    value = nextValue;
                    j++;
                }
            }

            tokens.push_back({i, j - i, value, true});
            i = j;
        }

        // Case 2: Diputs zero.
        else if (c == 'O') {
            tokens.push_back({i, 1, 0, false});
            i++;
        }

        // Case 3: nonzero Diputs number.
        else if (digitId[c] != -1) {
            size_t j = i;

            // Significance must not increase while reading left to right.
            int lastSignificance = 8;

            // Counts of digits used in this token.
            int count[9] = {};

            while (j < n) {
                unsigned char ch = text[j];
                int id = digitId[ch];

                // Stop if not a Diputs digit.
                if (id == -1) {
                    break;
                }

                // Stop if significance increases.
                if (id > lastSignificance) {
                    break;
                }

                // Stop if this digit exceeds its maximum count.
                if (count[id] >= maxCount[id]) {
                    break;
                }

                count[id]++;
                lastSignificance = id;
                j++;
            }

            long long value = diputsToDecimal(i, j);
            tokens.push_back({i, j - i, value, false});
            i = j;
        }

        // Case 4: ordinary text.
        else {
            i++;
        }
    }

    // If the number of tokens is odd, sort their values.
    if (tokens.size() % 2 == 1) {
        vector<long long> values;
        values.reserve(tokens.size());

        for (const Token& token : tokens) {
            values.push_back(token.value);
        }

        sort(values.begin(), values.end());

        for (size_t i = 0; i < tokens.size(); i++) {
            tokens[i].value = values[i];
        }
    }

    // Reconstruct output.
    string output;
    size_t cursor = 0;

    for (const Token& token : tokens) {
        // Copy unchanged text before this token.
        output.append(text, cursor, token.start - cursor);

        // Convert to the opposite notation.
        if (token.wasDecimal) {
            output += decimalToDiputs(token.value);
        } else {
            output += to_string(token.value);
        }

        // Skip original token.
        cursor = token.start + token.length;
    }

    // Copy the remaining text.
    output.append(text, cursor, string::npos);

    cout << output;

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def main():
    # Read the whole input.
    text = sys.stdin.read()

    # Diputs digits from least significant to most significant.
    digits = "_.,-~='^\""

    # Maximum allowed counts for each digit.
    max_count = [2, 3, 5, 7, 11, 13, 17, 19, 23]

    # place[i] is the value of one occurrence of digit i.
    place = [1]

    for cnt in max_count:
        place.append(place[-1] * (cnt + 1))

    # Maximum representable number.
    max_value = place[9] - 1

    # Character to Diputs digit index.
    digit_id = {ch: i for i, ch in enumerate(digits)}

    def is_decimal_digit(ch):
        return "0" <= ch <= "9"

    def diputs_to_decimal(s):
        """
        Convert a valid Diputs token to decimal.
        """
        value = 0

        for ch in s:
            value += place[digit_id[ch]]

        return value

    def decimal_to_diputs(n):
        """
        Convert a decimal integer to Diputs notation.
        """
        if n == 0:
            return "O"

        count = [0] * 9

        # Extract mixed-radix digits.
        for i in range(9):
            count[i] = (n // place[i]) % (max_count[i] + 1)

        result = []

        # Output from most significant to least significant.
        for i in range(8, -1, -1):
            if count[i] > 0:
                result.append(digits[i] * count[i])

        return "".join(result)

    # Each token is stored as:
    # [start_position, length, numeric_value, was_decimal]
    tokens = []

    n = len(text)
    i = 0

    # Greedy scan.
    while i < n:
        ch = text[i]

        # Case 1: decimal number.
        if is_decimal_digit(ch):
            j = i
            value = 0

            # Decimal numbers cannot have leading zeroes.
            # Therefore '0' is one complete token.
            if ch == "0":
                j = i + 1
                value = 0
            else:
                # Consume as many digits as possible while value is valid.
                while j < n and is_decimal_digit(text[j]):
                    next_value = value * 10 + (ord(text[j]) - ord("0"))

                    if next_value > max_value:
                        break

                    value = next_value
                    j += 1

            tokens.append([i, j - i, value, True])
            i = j

        # Case 2: Diputs zero.
        elif ch == "O":
            tokens.append([i, 1, 0, False])
            i += 1

        # Case 3: nonzero Diputs number.
        elif ch in digit_id:
            j = i

            # Significance must be non-increasing from left to right.
            last_significance = 8

            # Counts of digits in this token.
            count = [0] * 9

            while j < n:
                current = text[j]

                # Stop if current character is not a Diputs digit.
                if current not in digit_id:
                    break

                idx = digit_id[current]

                # Stop if significance increases.
                if idx > last_significance:
                    break

                # Stop if this digit exceeds the maximum count.
                if count[idx] >= max_count[idx]:
                    break

                count[idx] += 1
                last_significance = idx
                j += 1

            value = diputs_to_decimal(text[i:j])
            tokens.append([i, j - i, value, False])
            i = j

        # Case 4: ordinary text.
        else:
            i += 1

    # If there is an odd number of numbers, sort values.
    if len(tokens) % 2 == 1:
        values = sorted(token[2] for token in tokens)

        for idx, value in enumerate(values):
            tokens[idx][2] = value

    # Reconstruct output.
    result = []
    cursor = 0

    for start, length, value, was_decimal in tokens:
        # Copy unchanged text before this token.
        result.append(text[cursor:start])

        # Convert to opposite notation.
        if was_decimal:
            result.append(decimal_to_diputs(value))
        else:
            result.append(str(value))

        # Skip original token.
        cursor = start + length

    # Copy remaining text.
    result.append(text[cursor:])

    sys.stdout.write("".join(result))


if __name__ == "__main__":
    main()
```