分析

模拟赛送分题。

由于后面不会影响前面，所以考虑从后往前做。

发现影响一位的只有后面最大的字母，不好贪心，考虑 dp。

$dp_{i,j}$ 表示，考虑到第 $i$ 个位置（从后往前），后面最大的字母是 $j$ 的最小答案。

$val_i$ 表示字母 $i$ 的对应数字。

初始化 $f_{n+1,0}=0$。

转移是容易的：

1. $s_i \ne$ ?，转移容易：

   $$f_{i+1,j}+(s_i\ge j?1:-1)\times val_{s_i}\rarr f_{i,\max(j,s_i)}$$

2. $s_i =$ ?，将 $s_i$ 当成所有字母转移一遍。

构造方案时，$g_{i,j}$ 记录最优转移到 $f_{i,j}$ 的 $f_{i+1,k}$ 的 $k$。

对于每个 ? 的位置，$q_{i,j}$ 记录第 $i$ 个位置，将 $s_i$ 当成每个字母时最优转移到 $f_{i,j}$ 的字母是哪个。

通过这些辅助数组一直回退最优点在哪里，到 ? 的位置就填 $q_{i,j}$，回退时 $g_{i,j}\rarr j$。

时间复杂度在全 ? 时卡满，令 $V=26$（字母个数），复杂度 $O(nV^2)$。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,t,dp[N][26],f[N][26],p[26],q[N][26];
int val[26]={1,5,(int)1e1,(int)5e1,(int)1e2,(int)5e2,(int)1e3,(int)5e3,(int)1e4,(int)5e4,(int)1e5,(int)5e5,(int)1e6,(int)5e6,
			(int)1e7,(int)5e7,(int)1e8,(int)5e8,(int)1e9,
			(int)5e9,(int)1e10,(int)5e10,(int)1e11,(int)5e11,(int)1e12,(int)5e12};
string s;
bool mx(int &a,int b){
	a=max(a,b);
	return a==b;
}
//void checker(string a,int ans){
//	a=" "+a;
//	int maxn=0,anss=0;
//	for(int i=n;i>=1;i--){
//		if(a[i]>=maxn)maxn=a[i],anss+=val[a[i]-'A'];
//		else anss-=val[a[i]-'A'];
//	}
//	if(anss!=ans){
//		cout<<"Wrong: string "<<a<<" ans "<<ans<<" real "<<anss<<"\n";
//		assert(anss==ans);
//		exit(0);
//	}
//}
void solve(){
	cin>>s;
	n=s.size();
	s=" "+s;
	for(int j=0;j<=25;j++)dp[n+1][j]=-1e18; 
	dp[n+1][0]=0;
	for(int i=n;i>=1;i--){
		for(int j=0;j<=25;j++)dp[i][j]=f[i][j]=p[j]=-1e18; 
		if(s[i]!='?'){
			for(int j=0;j<=25;j++){
				if(mx(dp[i][max(j,(int)s[i]-'A')],dp[i+1][j]+(s[i]-'A'>=j?1:-1)*val[s[i]-'A'])){
					f[i][max(j,(int)s[i]-'A')]=j;
				}
			}
		}else {
			for(int k=0;k<=25;k++){
				s[i]=k+'A';
				for(int j=0;j<=25;j++){
					if(mx(dp[i][max(j,(int)s[i]-'A')],dp[i+1][j]+(s[i]-'A'>=j?1:-1)*val[s[i]-'A'])){
						f[i][max(j,(int)s[i]-'A')]=j;
					}
					int te=max(j,(int)s[i]-'A');
					if(dp[i][te]>p[te])p[te]=dp[i][te],q[i][te]=k;
				}
			}
			s[i]='?';
		}
	}
	int ans=-1e18,now;
	for(int i=0;i<=25;i++){
		if(mx(ans,dp[1][i])){
			now=i;
		}
	}
	string anss="";
	for(int i=1;i<=n;i++){
		anss+=(s[i]=='?'?char(q[i][now]+'A'):s[i]);
		now=f[i][now];
	}
	cout<<ans<<'\n'<<anss<<"\n";
//	checker(anss,ans);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}