#include "paint.h"
#include <iostream>
#include<string>
#include<vector>
#define MAXN 200005
#define MAXK 105
using namespace std;
int N, K, whitesum[MAXN], canblack[MAXN], black;
bool dp[MAXN][MAXK], done[MAXN][MAXK], canwhite[MAXN];
string s;
vector <int> c;
bool gen(int i, int j) {
if (i >= N && j == K) {return(1);}
if (i >= N && j < K) {return(0);}
if (done[i][j]) {return(dp[i][j]);}
done[i][j]=true;
if (s[i] != 'X' && gen(i+1,j)) {
dp[i][j]=true;
canwhite[i]=true;
}
if (j < K && i + c[j] <= N) {
bool can = true;
if (whitesum[i+c[j]] - whitesum[i] > 0 || (i+c[j] != N && s[i+c[j]] == 'X')) {
can=false;
}
if (can && gen(i+c[j]+1, j+1)) {
dp[i][j]=true;
canblack[i]++;
canblack[i+c[j]]--;
canwhite[i+c[j]]=true;
}
}
return(dp[i][j]);
}
string solve_puzzle(string S, vector<int> C) {
N=S.size(), K=C.size();
s = S, c = C;
for (int i=1; i<=N; i++) {
whitesum[i]=whitesum[i-1] + (S[i-1] == '_');
}
gen(0,0);
string Sol;
for (int i=0; i<N; i++) {
black+=canblack[i];
if (black && canwhite[i]) {
Sol.push_back('?');
} else if (black) {
Sol.push_back('X');
} else {
Sol.push_back('_');
}
}
return(Sol);
}
