#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
const int inf=1000001000;
const int MAXN=200010, K=103;
int n, m, k;
bool dp[MAXN][K], pd[MAXN][K];
int C[K];
int ps[MAXN][2], res[MAXN];
string S, ans;
bool check(int i, int j, int t){
int l=i-t, r=i-t+1+C[j];
if (r>n+1 || S[l]=='X' || S[r]=='X' || ps[r-1][0]!=ps[l][0]) return 0;
if (l && !dp[l-1][j-1]) return 0;
if (!l && j>1) return 0;
if (r<=n && !pd[r+1][j+1]) return 0;
if (r==n+1 && j<k) return 0;
return 1;
}
string solve_puzzle(string _S, vector<int> _C) {
S=_S;
n=S.size();
S="#"+S+"#";
for (int i=1; i<=n+1; i++){
ps[i][0]=ps[i-1][0];
ps[i][1]=ps[i-1][1];
if (S[i]=='_') ps[i][0]++;
if (S[i]=='X') ps[i][1]++;
}
k=_C.size();
for (int i=1; i<=k; i++) C[i]=_C[i-1];
dp[0][0]=1;
for (int i=1; i<=n; i++){
if (S[i]!='X'){
for (int j=0; j<=k; j++)
dp[i][j]=dp[i-1][j];
}
for (int j=1; j<=k; j++) if (C[j]<=i){
if (ps[i][0]==ps[i-C[j]][0] && S[i-C[j]]!='X')
dp[i][j]|=dp[i-C[j]-(C[j]<i)][j-1];
}
}
pd[n+1][k+1]=1;
for (int i=n; i; i--){
if (S[i]!='X'){
for (int j=1; j<=k+1; j++)
pd[i][j]=pd[i+1][j];
}
for (int j=1; j<=k; j++) if (i+C[j]<=n+1){
if (ps[i-1][0]==ps[i+C[j]-1][0] && S[i+C[j]]!='X')
pd[i][j]|=pd[min(n+1, i+C[j]+1)][j+1];
}
}
for (int i=1; i<=n; i++) for (int j=1; j<=k; j++) if (check(i, j, 1)) res[i]++, res[i+C[j]]--;
for (int i=1; i<=n; i++) res[i]+=res[i-1];
for (int i=1; i<=n; i++){
if (S[i]!='.'){
ans+=S[i];
continue ;
}
int f0=0, f1=0;
for (int j=0; j<=k; j++){
if (dp[i-1][j] && pd[i+1][j+1]){
f0=1;
break ;
}
}
if (res[i]) f1=1;
if (f0+f1==1){
if (f0) ans+='_';
else ans+='X';
}
else ans+='?';
}
return ans;
}
