#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
const int mxN = 2e5+5;
const int mxK = 105;
int N, K, C[mxK];
string S;
int pw[mxN];
int l[2][mxN][mxK], r[2][mxN][mxK], w[mxN], b[mxN];
string solve_puzzle(string s, vector<int> c) {
N = SZ(s), S = '^' + s, K = SZ(c);
FOR(i,1,K){ C[i] = c[i-1]; }
pw[0] = 0;
FOR(i,1,N) pw[i] = pw[i-1] + (S[i] == '_');
C[0] = N+10; // make sure C[0] cannot be used
FOR(f,0,1) { l[f][0][0] = 1; FOR(j,1,K) l[f][0][j] = 0; }
FOR(i,1,N){
FOR(j,0,K){
l[1][i][j] = (S[i] != 'X' && (l[1][i-1][j] || l[0][i-1][j]));
l[0][i][j] = (i-C[j]+1 >= 1 && pw[i]-pw[i-C[j]] == 0 && l[1][i-C[j]][j-1]);
}
}
C[N+1] = N+10; // make sure C[N+1] cannot be used
FOR(f,0,1) { r[f][N+1][K+1] = 1; FOR(j,1,K) r[f][N+1][j] = 0; }
RFOR(i,N,1){
FOR(j,1,K+1){
r[1][i][j] = (S[i] != 'X' && (r[1][i+1][j] || r[0][i+1][j]));
r[0][i][j] = (i+C[j]-1 <= N && pw[i+C[j]-1]-pw[i-1] == 0 && r[1][i+C[j]][j+1]);
}
}
FOR(i,1,N){
FOR(j,0,K){
if (l[1][i][j] && r[1][i][j+1]) w[i] = 1;
if (l[0][i][j] && r[1][i+1][j+1]) ++b[i-C[j]+1], --b[i+1];
}
}
string ans(N,'?');
FOR(i,1,N){
b[i] += b[i-1];
ans[i-1] = (w[i] == 0 ? 'X' : (b[i] == 0 ? '_' : '?'));
}
return ans;
}
