#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "paint.h"
using namespace std;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<vector<bool>> solvedp(vector<int>w,vector<int>b,vector<int>c){
int n = sz(w), k = sz(c);
vector<int>wpref(n+1);
for(int i=1;i<=n;++i)wpref[i]=wpref[i-1]+w[i-1];
vector<vector<bool>>dp(n+1,vector<bool>(k+1,0));
dp[0][0] = true;
for(int i=1;i<=n;++i)dp[i][0] = dp[i-1][0]&&!b[i-1];
for(int j=1;j<=k;++j){
for(int i=1;i<=n;++i){
if(!b[i-1]){
if(dp[i-1][j])dp[i][j] = true;
}
if(!w[i-1]){
if(c[j-1] > i)continue;
if(wpref[i]-wpref[i-c[j-1]] > 0)continue;
if(i!=c[j-1]&&b[i-c[j-1]-1])continue;
if(dp[max(0,i-c[j-1]-1)][j-1])dp[i][j] = true;
}
}
}
return dp;
}
string solve_puzzle(string s,vector<int>c){
int n = sz(s), k = sz(c);
vector<int>w(n), b(n);
for(int i=0;i<n;++i)w[i] = (s[i]=='_');
for(int i=0;i<n;++i)b[i] = (s[i]=='X');
vector<vector<bool>>prefixdp = solvedp(w,b,c);
reverse(all(b));reverse(all(w));reverse(all(c));
vector<vector<bool>>suffixdp = solvedp(w,b,c);
reverse(all(b));reverse(all(w));reverse(all(c));
// for(int j=0;j<=k;++j)
// for(int i=1;i<=n;++i)
// cout<<prefixdp[i][j]<<" \n"[i==n];
// for(int j=0;j<=k;++j)
// for(int i=1;i<=n;++i)
// cout<<suffixdp[i][j]<<" \n"[i==n];
vector<bool>canwhite(n),canblack(n);
for (int i=0; i<n; ++i) for (int j=0; j<=k; ++j)
if (!b[i] && prefixdp[i][j] && suffixdp[n-i-1][k-j]) canwhite[i] = true;
vector<int>intervals(n+1);
vector<int>wpref(n+1);
for(int i=1;i<=n;++i)wpref[i] = wpref[i-1] + w[i-1];
for (int j=0; j<k; ++j) {
for (int start=0; start+c[j]<=n; ++start) {
if (start > 0 && b[start-1]) continue;
if (start+c[j]<n && b[start+c[j]]) continue;
if (wpref[start+c[j]] > wpref[start]) continue;
if (prefixdp[max(0,start-1)][j] && suffixdp[max(0,n-start-c[j]-1)][k-j-1]) {
intervals[start] += 1;
intervals[start+c[j]] -= 1;
}
}
}
// cout<<"alive"<<endl;
int sum = 0;
for(int i=0;i<n;++i){
sum += intervals[i];
if(sum>0)canblack[i] = true;
}
for(int i=0;i<n;++i){
// cout<<canblack[i]<<" "<<canwhite[i]<<endl;
if(canblack[i]&&canwhite[i])s[i]='?';
else if(canblack[i])s[i]='X';
else s[i]='_';
}
return s;
}
// int main(){
// string s;int k;cin>>s>>k;
// vector<int>c(k);
// for(auto& x:c)cin>>x;
// cout<<solve_puzzle(s,c)<<endl;
// }
