#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,bef[200001],aft[200001],mark[200001],qs[200001],rqs[200001];
bool dp1[200001][101],dp2[200001][101];
bool canX[200001],canY[200001];
string ans;
string solve_puzzle(string s, vector<int> c) {
n=s.size();
m=c.size();
int before=-1,after=n;
for (int i=0; i<n; ++i) {
if (i) qs[i]+=qs[i-1];
if (s[i]=='X') ++qs[i];
if (s[i]=='_') before=i;
bef[i]=before;
}
for (int i=n-1; i>=0; --i) {
if (i!=n-1) rqs[i]+=rqs[i+1];
if (s[i]=='X') ++rqs[i];
if (s[i]=='_') after=i;
aft[i]=after;
}
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
if (i && s[i]!='X') dp1[i][j]=dp1[i-1][j];
if (i-bef[i]>=c[j]) {
if (i-c[j]-1>=0 && dp1[i-c[j]-1][j-1]) dp1[i][j]=true;
else if (j==0) {
if (i-c[j]>=0) {
if (qs[i-c[j]]==0) dp1[i][j]=true;
} else dp1[i][j]=true;
}
}
}
}
for (int i=n-1; i>=0; --i) {
for (int j=0; j<m; ++j) {
if (i!=n-1 && s[i]!='X') dp2[i][j]=dp2[i+1][j];
if (aft[i]-i>=c[j]) {
if (i+c[j]+1<n && dp2[i+c[j]+1][j+1]) {
dp2[i][j]=true;
if (j==0 || (i>=2 && dp1[i-2][j-1])) ++mark[i], --mark[i+c[j]];
} else if (j==m-1) {
if (i+c[j]<n) {
if (rqs[i+c[j]]==0) {
dp2[i][j]=true;
if (j==0 || (i>=2 && dp1[i-2][j-1])) ++mark[i], --mark[i+c[j]];
}
} else {
dp2[i][j]=true;
if (j==0 || (i>=2 && dp1[i-2][j-1])) ++mark[i], --mark[i+c[j]];
}
}
}
}
}
for (int i=0; i<n; ++i) {
mark[i]+=mark[i-1];
if (mark[i]) canX[i]=true;
if ((i>=1 && dp1[i-1][m-1]) || (i<=n-2 && dp2[i+1][0])) canY[i]=true;
for (int j=0; j<m-1; ++j) {
if (i!=0 && i!=n-1 && dp1[i-1][j] && dp2[i+1][j+1]) canY[i]=true;
}
}
for (int i=0; i<n; ++i) {
if (s[i]=='X' || s[i]=='_') ans+=s[i];
else {
if (canX[i] && canY[i]) ans+='?';
else if (canX[i]) ans+='X';
else ans+='_';
}
}
return ans;
}
