<|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;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string input_text;

void read() {
    stringstream buffer;
    buffer << cin.rdbuf();
    input_text = buffer.str();
}

void solve() {
    // Pure implementation. Tokenize the input into decimal numbers, Diputs
    // numbers and "other" characters. A Diputs digit is one of `_.,-~='^"`
    // (least to most significant); a valid Diputs representation lists digits
    // in non-increasing significance and respects per-digit max quantities, so
    // we parse greedily under both constraints. Decimal numbers are parsed
    // greedily up to the Diputs maximum value, with a leading '0' forming the
    // single number 0. The encoding is a mixed-radix system, so conversion in
    // either direction is a small loop instead of enumerating ~836M values.
    // After tokenizing we flip each token's notation, optionally sort the
    // values when the total count is odd, and emit with original separators.

    const string diputs_chars = "_.,-~='^\"";
    const int max_counts[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

    int64_t products[10];
    products[0] = 1;
    for(int i = 0; i < 9; i++) {
        products[i + 1] = products[i] * (max_counts[i] + 1);
    }

    int64_t max_num = products[9] - 1;

    array<int, 256> sig_of;
    sig_of.fill(-1);
    for(int i = 0; i < 9; i++) {
        sig_of[(unsigned char)diputs_chars[i]] = i;
    }

    auto diputs_to_decimal = [&](size_t start, size_t end) -> int64_t {
        int64_t value = 0;
        for(size_t k = start; k < end; k++) {
            value += products[sig_of[(unsigned char)input_text[k]]];
        }
        return value;
    };

    auto decimal_to_diputs = [&](int64_t n) -> string {
        if(n == 0) {
            return "O";
        }
        int counts[9];
        for(int i = 0; i < 9; i++) {
            counts[i] = (n / products[i]) % (max_counts[i] + 1);
        }
        string result;
        for(int i = 8; i >= 0; i--) {
            result.append(counts[i], diputs_chars[i]);
        }
        return result;
    };

    struct token {
        size_t start;
        size_t length;
        int64_t value;
        bool was_decimal;
    };

    vector<token> tokens;

    size_t n = input_text.size();
    for(size_t i = 0; i < n;) {
        unsigned char c = input_text[i];
        if(isdigit(c)) {
            size_t j = i;
            int64_t value = 0;
            if(c == '0') {
                j = i + 1;
            } else {
                while(j < n && isdigit((unsigned char)input_text[j])) {
                    int64_t next_val = value * 10 + (input_text[j] - '0');
                    if(next_val > max_num) {
                        break;
                    }
                    value = next_val;
                    j++;
                }
            }
            tokens.push_back({i, j - i, value, true});
            i = j;
        } else if(c == 'O') {
            tokens.push_back({i, 1, 0, false});
            i++;
        } else if(sig_of[c] >= 0) {
            size_t j = i;
            int last_sig = 8;
            int counts[9] = {};
            while(j < n) {
                int s = sig_of[(unsigned char)input_text[j]];
                if(s < 0 || s > last_sig || counts[s] >= max_counts[s]) {
                    break;
                }
                counts[s]++;
                last_sig = s;
                j++;
            }
            tokens.push_back({i, j - i, diputs_to_decimal(i, j), false});
            i = j;
        } else {
            i++;
        }
    }

    if(tokens.size() % 2 == 1) {
        vector<int64_t> values;
        values.reserve(tokens.size());
        for(auto& t: tokens) {
            values.push_back(t.value);
        }
        sort(values.begin(), values.end());
        for(size_t k = 0; k < tokens.size(); k++) {
            tokens[k].value = values[k];
        }
    }

    string result;
    result.reserve(input_text.size() * 2);
    size_t cursor = 0;
    for(auto& t: tokens) {
        while(cursor < t.start) {
            result += input_text[cursor++];
        }
        if(t.was_decimal) {
            result += decimal_to_diputs(t.value);
        } else {
            result += to_string(t.value);
        }
        cursor = t.start + t.length;
    }

    while(cursor < input_text.size()) {
        result += input_text[cursor++];
    }

    cout << result;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def main():
    # Read the entire input as one string.
    text = sys.stdin.read()

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

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

    # products[i] is the mixed-radix place value of digit i.
    products = [1]

    # Build place values.
    # products[i + 1] = products[i] * number_of_possible_counts_for_digit_i
    for cnt in max_counts:
        products.append(products[-1] * (cnt + 1))

    # Maximum representable value.
    max_num = products[9] - 1

    # Map each Diputs character to its significance index.
    sig_of = {ch: i for i, ch in enumerate(diputs_chars)}

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

        # Each character contributes its place value.
        for ch in s:
            value += products[sig_of[ch]]

        return value

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

        counts = [0] * 9

        # Extract mixed-radix digits.
        for i in range(9):
            counts[i] = (n // products[i]) % (max_counts[i] + 1)

        result = []

        # Output from most significant digit to least significant digit.
        for i in range(8, -1, -1):
            if counts[i]:
                result.append(diputs_chars[i] * counts[i])

        return "".join(result)

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

    n = len(text)
    i = 0

    # Greedily scan input from left to right.
    while i < n:
        c = text[i]

        # Case 1: decimal number.
        if c.isdigit():
            j = i
            value = 0

            # Decimal numbers may not have leading zeroes.
            # Therefore '0' is always a token of length 1.
            if c == "0":
                j = i + 1
            else:
                # Extend while the token remains a valid decimal number
                # not exceeding max_num.
                while j < n and text[j].isdigit():
                    next_value = value * 10 + (ord(text[j]) - ord("0"))

                    # Stop before exceeding the representable range.
                    if next_value > max_num:
                        break

                    value = next_value
                    j += 1

            # Store decimal token.
            tokens.append([i, j - i, value, True])

            # Continue after token.
            i = j

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

        # Case 3: nonzero Diputs number.
        elif c in sig_of:
            j = i

            # Previous significance index.
            # A valid Diputs representation must have non-increasing
            # significance from left to right.
            last_sig = 8

            # Counts used in this token.
            counts = [0] * 9

            # Greedily extend the Diputs token.
            while j < n:
                ch = text[j]

                # Stop if not a Diputs digit.
                if ch not in sig_of:
                    break

                s = sig_of[ch]

                # Stop if significance increases.
                if s > last_sig:
                    break

                # Stop if this digit has reached its maximum allowed count.
                if counts[s] >= max_counts[s]:
                    break

                # Accept this character.
                counts[s] += 1

                # Future characters must be no more significant.
                last_sig = s

                # Advance end position.
                j += 1

            # Convert the parsed substring to decimal.
            value = diputs_to_decimal(text[i:j])

            # Store Diputs token.
            tokens.append([i, j - i, value, False])

            # Continue after token.
            i = j

        # Case 4: ordinary non-number 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)

        # Put sorted values back into token positions.
        # The original notation type at each position is preserved.
        for idx, value in enumerate(values):
            tokens[idx][2] = value

    # Build the final output.
    result = []
    cursor = 0

    for start, length, value, was_decimal in tokens:
        # Copy unchanged text before this token.
        if cursor < start:
            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()
```
