#include "paint.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5;
const int mxk=103;
const int inf=1e9;
bool dp1[mxn][mxk][2] = {} ,dp2[mxn][mxk][2] = {};
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
s = '#' + s;
c.insert(c.begin(),0);
int lw = 0;
dp1[0][0][0] = true;
dp2[n+1][k+1][0] = true;
for(int i = 1 ; i <= n; i++) {
if(s[i] != 'X') {
dp1[i][0][0] = dp1[i-1][0][0];
for(int j = 1; j <=k; j++) {
dp1[i][j][0] = dp1[i-1][j][0] || ((lw <= i - c[j] - 1) && dp1[i - c[j] - 1][j - 1][0]);
}
}
if(s[i] != '_') {
for(int j = 1; j <= k; j++) {
dp1[i][j][1] = (i - c[j] >= lw) && dp1[i - c[j]][j - 1][0];
}
} else {
lw = i;
}
}
int rw = n + 1;
for(int i = n ; i >= 1; i--) {
if(s[i] != 'X') {
dp2[i][k+1][0] = dp2[i+1][k+1][0];
for(int j = 1; j <=k; j++) {
dp2[i][j][0] = dp2[i+1][j][0] || ((rw >= i + c[j] + 1) && dp2[i + c[j] + 1][j + 1][0]);
}
}
if(s[i] != '_') {
for(int j = 1; j <= k; j++) {
dp2[i][j][1] = (i + c[j] <= rw) && dp2[i + c[j]][j + 1][0];
}
} else {
rw = i;
}
}
//cout<<dp2[11][3][0]<<" --- "<<dp1[10][2][0]<<endl;
int t1[n+1] = {};
int t2[n+1] = {};
for(int i = 1; i <= n; i++) {
int mx = -1;
for(int j = 1; j <= k; j++) {
if(dp1[i][j][0] && (dp2[i][j+1][0] || dp2[i+1][j+1][1])) t1[i] = 1;
if(dp1[i][j][1] && dp2[i+1][j+1][0]) mx = max(mx,c[j]);
}
if(dp1[i][0][0] && (dp2[i+1][1][0] || dp2[i+1][1][1])) t1[i] = 1;
for(int j = i; j > i - mx; j--) t2[j] = 1;
}
string res = "";
for(int i = 1; i <= n; i++) {
if(t1[i] && t2[i]) res+='?';
else if(t1[i]) res+='_';
else res+='X';
}
return res;
}
