Problem Description

Translated from ROI 2021 D2T1。

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.

Input Format

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$。

Output Format

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.

4
BBBC
????
A?B?C?D
YYYYY?

-5
BBBC
20000000000000
ZZZZ
15000000000034
AZBZCZD
6000000000000
YYYYYY

Hint

Let $S=\sum\limits^{t}_{i=1}|s_i|$。

Translated by ChatGPT 5