#P15918. [Roi2021]莫斯科数字

[Roi2021]莫斯科数字

题目描述

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

莫斯科数字的数字符号是大写英文字母 A 到 Z。一个数由若干个这样的符号组成。每个符号对应的值如下:

字母 值 字母 值 字母 值 字母 值
A 1 H 5⋅1035\cdot 10^3 O 10710^7 V 5⋅10105\cdot 10^{10}
B 5 I 10410^4 P 5⋅1075\cdot 10^7 W 101110^{11}
C 10 J 5⋅1045\cdot 10^4 Q 10810^8 X 5⋅10115\cdot 10^{11}
D 50 K 10510^5 R 5⋅1085\cdot 10^8 Y 101210^{12}
E 100 L 5⋅1055\cdot 10^5 S 10910^9 Z 5⋅10125\cdot 10^{12}
F 500 M 10610^6 T 5⋅1095\cdot 10^9
G 10310^3 N 5⋅1065\cdot 10^6 U 101010^{10}

一个莫斯科数字的值等于其中所有符号贡献之和。每个符号的贡献可能为正,也可能为负:

  • 若该符号右侧不存在严格更大的符号,则它的贡献等于自身值;
  • 否则,它的贡献等于自身值的相反数。

例如:

  • BBA 的值为 5+5+1=115+5+1=11;
  • BBBC 的值为 −5+(−5)+(−5)+10=−5-5+(-5)+(-5)+10=-5;
  • ABC 的值为 −1+(−5)+10=4-1+(-5)+10=4;
  • BAC 的值为 −5+(−1)+10=4-5+(-1)+10=4;
  • ACA 的值为 −1+10+1=10-1+10+1=10。

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

输入格式

第一行包含一个整数 tt,表示模板数量。

接下来 tt 行,每行包含一个字符串 sis_i,由大写英文字母和字符 ? 组成,表示一个模板。

输出格式

对每个模板输出两行:

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

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

数据范围

1≤t≤500001\le t\le 50000

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

样例输入

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

样例输出

-5
BBBC
20000000000000
ZZZZ
15000000000034
AZBZCZD
6000000000000
YYYYYY

子任务

记所有字符串总长度为 SS。

子任务 分值 限制 依赖 检查信息
1 6 S≤1000S\le 1000,sis_i 不含 ? 无 第一处错误
2 9 S≤3⋅105S\le 3\cdot 10^5,sis_i 不含 ? 1
3 40 S≤1000S\le 1000,每个 sis_i 至多含 3 个 ?
4 20 S≤1000S\le 1000 U, 1, 3
5 25 S≤3⋅105S\le 3\cdot 10^5 U, 1-4