#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
map< pair <int,pair<int,int>>, bool> cache;
map< pair<int,pair<int,int>>, bool> known;
bool solvable(string & s, string & res, vector<int>& c, int remX, int spos, int cpos){
pair <int,pair<int,int>> pos = {remX, {spos, cpos}};
if (known[pos]) return cache[pos];
//cout << "at " << spos << " with " << remX <<"/" << c[cpos] << " remaining" << endl;
if (spos == s.size()) return cpos == c.size() -1 && remX <= 0;
if (remX == 0 && s[spos] != '_' && s[spos] != '.') {
return 0;
}
if (remX > 0 && s[spos] != 'X' && s[spos] != '.') {
return 0;
}
if (remX >= 0) {
if (solvable(s,res,c, remX - 1, spos+1, cpos)){
if (remX == 0 && res[spos] == '.') res[spos] = '_';
if (remX == 0 && res[spos] == 'X') res[spos] = '?';
if (remX > 0 && res[spos] == '.') res[spos] = 'X';
if (remX > 0 && res[spos] == '_') res[spos] = '?';
cache[pos] = 1;
known[pos] = 1;
return 1;
}
known[pos] = 1;
cache[pos] = 0;
return 0;
}else{
bool sol = 0;
if (s[spos] != 'X' && solvable(s,res,c, remX, spos+1, cpos)){
//cout << "possible to skip at " << spos << endl;
if (res[spos] == '.') res[spos] = '_';
if (res[spos] == 'X') res[spos] = '?';
sol = 1;
}
if (cpos +1< c.size())
{
sol = solvable(s,res,c, c[cpos+1], spos, cpos+1) || sol;
cache[pos] = sol;
known[pos] = 1;
return sol;
}
known[pos] = 1;
cache[pos] = sol;
return sol;
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
string res = s;
solvable(s,res,c, -1, 0, -1);
return res;
}
