#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
string s;
vector<int> c;
int n;
int k;
vector<bool> defB;
vector<bool> mayB;
vector<bool> defW;
vector<bool> mayW;
vector<vector<bool>> visited;
vector<vector<bool>> valid;
bool solve(int clueIdx, int strIdx) {
if(strIdx >= n) return clueIdx == k;
if(clueIdx == k) {
for(int i = strIdx; i < n; i++)
if(s[i] == 'X') return false;
for(int i = strIdx; i < n; i++)
mayW[i] = true;
return true;
}
if(visited[clueIdx][strIdx]) return valid[clueIdx][strIdx];
visited[clueIdx][strIdx] = true;
bool dontpick = s[strIdx] != 'X' && solve(clueIdx, strIdx + 1);
// cout << dontpick << endl;
if(dontpick) mayW[strIdx] = true;
for(int i = 0; i < c[clueIdx]; i++) {
if(strIdx+i >= n || s[strIdx+i] == '_') return valid[clueIdx][strIdx] = dontpick;
}
if(strIdx+c[clueIdx] < n && s[strIdx+c[clueIdx]] == 'X') return valid[clueIdx][strIdx] = dontpick;
bool pick = solve(clueIdx + 1, strIdx+c[clueIdx]+1);
// cout << pick << endl<<endl;
if(pick) {
for(int i = 0; i < c[clueIdx]; i++)
mayB[strIdx + i] = true;
if(strIdx+c[clueIdx] < n)
mayW[strIdx+c[clueIdx]] = true;
}
return valid[clueIdx][strIdx] = pick || dontpick;
}
string solve_puzzle(string s_, vector<int> c_) {
s = s_;
c = c_;
n = s.size();
k = c.size();
defB.resize(n, false);
mayB.resize(n, false);
defW.resize(n, false);
mayW.resize(n, false);
visited.resize(k, vector<bool>(n));
valid.resize(k, vector<bool>(n));
string ans = "";
solve(0,0);
// for(int i = 0; i < n; i++) cout << mayB[i] << " "; cout << endl;
// for(int i = 0; i < n; i++) cout << mayW[i] << " "; cout << endl;
for(int i = 0; i < n; i++) {
if (mayB[i] && mayW[i]) ans += "?";
else if(mayB[i] && !mayW[i]) ans += "X";
else if(!mayB[i] && mayW[i]) ans += "_";
else if(!mayB[i] && !mayW[i]) ans += ".";
}
return ans;
}
