P11092 [ROI 2021] Moscow Numbers (Day 2)

Translated from [ROI 2021 D2T1](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf)。 You may be familiar with Roman numerals, and you may also have heard the saying that Moscow is the Third Rome, so we proudly introduce Moscow numbers. This is an advanced version of Roman numerals and is similar to it. In the Moscow number system, numbers are represented by uppercase English letters `A` to `Z`. Each letter corresponds to a specific value:  The rules of Moscow numbers are as follows: the value of a number equals the sum of the values of its letters. A letter can contribute positively or negatively. If there is no letter greater than it to its right, then its contribution equals its own value; otherwise, its contribution equals the negation of its own value. For example: - The value of `BBA` is $5 + 5 + 1 = 11$； - The value of `BBBC` is $-5 + (-5) + (-5) + 10 = -5$； - The value of `ABC` is $-1 + (-5) + 10 = 4$； - The value of `BAC` is $-5 + (-1) + 10 = 4$； - The value of `ACA` is $-1 + 10 + 1 = 10$； - The value of `CFF` is $-10 + 500 + 500 = 990$。 You are given some numbers, each consisting of uppercase English letters (i.e., Moscow numbers), but some positions have been replaced by question marks. For each number, determine the maximum possible value that can be obtained after replacing each question mark with a Moscow-number letter.

The first line contains an integer $t$, the number of test cases, i.e., the number of given numbers ($1 \le t \le 50000$)。 The next $t$ lines each contain a string $s_i$ consisting of uppercase English letters and question marks. The sum of lengths of all strings does not exceed $300000$。

For each input, output two lines, both describing the maximum result after replacing the question marks with Moscow-number letters. The first line is the maximum value in decimal. The second line is the corresponding maximum Moscow number after replacement.

Let $S=\sum\limits^{t}_{i=1}|s_i|$。 | Subtask | Score | $S\le$ | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1$ | $6$ | $1000$ | $s_i$ does not contain `?` | | $2$ | $9$ | $3\times10^5$ | $s_i$ does not contain `?` | | $3$ | $40$ | $1000$ | $s_i$ contains no more than three `?` | | $4$ | $20$ | $1000$ | | | $5$ | $25$ | $3\times10^5$ | | Translated by ChatGPT 5