题目描述

你大概熟悉罗马数字，也很可能听过“莫斯科是第三罗马”这句话。因此，出题人仿照罗马数字设计了一种进阶版本：莫斯科数字。

莫斯科数字的数字符号是大写英文字母 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$。

现在给出若干个数字模板。每个模板是一个由大写英文字母和问号 ? 组成的字符串。对每个模板，你需要把每个 ? 替换成 A 到 Z 中的某个字母，使得到的莫斯科数字的值尽可能大。

输入格式

第一行包含一个整数 $t$，表示模板数量。

接下来 $t$ 行，每行包含一个字符串 $s_i$，由大写英文字母和字符 ? 组成，表示一个模板。

输出格式

对每个模板输出两行：

第一行输出该模板能得到的最大值，使用十进制表示。
第二行输出一种达到最大值的替换结果，即把模板中的所有 ? 替换为大写英文字母后的字符串。

若有多种最优替换方案，输出任意一种即可。

数据范围

所有字符串总长度不超过 $300000$。

样例输入

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

样例输出

-5
BBBC
20000000000000
ZZZZ
15000000000034
AZBZCZD
6000000000000
YYYYYY

子任务

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