#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 2;
bitset<N> targB, targW;
vector<vector<bitset<N>>> dpB, dpW;
vector<vector<bool>> valid;
string solve_puzzle(string s, vector<int> c) {
int k = c.size(), n = s.size();
if(n > N)return "";
for(int i = 0; i < n; i++)targB[i+2] = s[i] == 'X', targW[i+2] = s[i] == '_';
dpB.resize(n+2); dpW.resize(n+2); valid.resize(n+2);
for(auto& i: dpB)i.resize(k+1);
for(auto& i: dpW)i.resize(k+1);
for(auto& i: valid)i.resize(k+1);
for(int i = 0; i <= n; i++)valid[i][0] = 1;
auto stringify = [n, k](int x, int y){
string ans = "";
for(int i = 2; i < n+2; i++){
//assert(dpW[n][k][i] || dpB[n][k][i]);
if(dpW[x][y][i] && dpB[x][y][i]) ans += '?';
else if(dpW[x][y][i]) ans += '_';
else if(dpB[x][y][i]) ans += 'X';
else ans += '!';
}
return ans;
};
for(int i = 2; i <= n+1; i++){
valid[i][0] = 1, dpW[i][0] = dpW[i-1][0];
dpW[i][0][i] = 1;
for(int j = 1; j <= k; j++){
if(i <= c[j-1] || !valid[i-c[j-1]-1][j-1])
continue;
valid[i][j] = 1;
dpW[i][j] = dpW[i-c[j-1]-1][j-1];
dpB[i][j] = dpB[i-c[j-1]-1][j-1];
//if(i != c[j-1])
dpW[i][j][i-c[j-1]] = 1;
for(int x = i-c[j-1]+1; x <= i; x++)dpB[i][j][x] = 1;
//cout << i-1 << " " << j << " " << stringify(i, j) << endl;
if(((dpB[i][j] & targW) | (dpW[i][j] & targB)).count())
dpW[i][j] = dpW[i-1][j], dpB[i][j] = dpB[i-1][j], valid[i][j] = valid[i-1][j], dpW[i][j][i] = 1;
else if(valid[i-1][j]) dpW[i][j] |= dpW[i-1][j], dpB[i][j] |= dpB[i-1][j], dpW[i][j][i] = 1;
if(dpW[i][j][i] && targB[i])valid[i][j] = 0;
//cout << i-1 << " " << j << " " << stringify(i, j) << endl;
}
}
return stringify(n+1, k);
}
