题目描述

译自 ROI 2021 Day2 T1. Московские числа

你可能听说过罗马数字，也可能听过「莫斯科是第三罗马」这句话。因此，我们决定借鉴罗马数字，发明一种高级版本——莫斯科数字。

莫斯科数字的数字是从 A 到 Z 的大写英文字母。一个数字是由多个字母组成的字符串。每个字母对应一个数值：

数字的值等于组成它的各个字母的贡献之和。字母的贡献可以是正的，也可以是负的。如果字母右边没有比它大的字母，那么它的贡献等于它的数值。否则，它的贡献等于它的数值取负。

例如：

• BBA 的值是 $5 + 5 + 1 = 11$；
• BBBC 的值是 $-5 + (-5) + (-5) + 10 = -5$；
• ABC 的值是 $-1 + (-5) + 10 = 4$；
• BAC 的值是 $-5 + (-1) + 10 = 4$；
• ACA 的值是 $-1 + 10 + 1 = 10$。

你得到了一些数字模板。每个模板是由大写英文字母和问号组成的字符串。对于每个模板，需要确定如果将每个问号替换为莫斯科数字的字母，能得到的最大数字是多少。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 5 \cdot 10^4)$，表示模板的数量。

接下来的 $t$ 行，每行是一个由大写英文字母和问号组成的字符串 $s_i$。所有字符串的总长度不超过 $3 \cdot 10^5$。

输出格式

对于每个模板，输出两行。第一行输出可以得到的最大数字的值（十进制表示）。第二行输出将问号替换为字母后的模板，使其达到最大值。

样例

输入

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

输出

-5
BBBC
20000000000000
ZZZZ
15000000000034
AZBZCZD
6000000000000
YYYYYY

数据范围与提示

令所有字符串的总长度为 $S$。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。