#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size(); int k = c.size();
vector<int> right(k+1,0), left(k+1,0);
int lenR = 0, lenL = 0;
for (int i = 1; i <= k; i++) {
if (i != 1) {lenR++; lenL++;}
while (count(s.begin()+lenR,s.begin()+lenR+c[i-1],'_') > 0) lenR++;
while (count(s.begin()+n-(lenL+c[k-i]),s.begin()+n-lenL,'_') > 0) lenL++;
lenR += c[i-1]; lenL += c[k-i];
right[i] = lenR; left[i] = lenL;
//cout << i << " " << right[i] << " " << left[i] << "\n";
}
vector<bool> white(n,false), black(n,false);
for (int pos = 0; pos < n; pos++) {
assert(s[pos] != 'X');
for (int i = 0; i <= k; i++) {
//if (pos == n-1) cout << shortest[pos-j] << "\n";
if (right[i] <= pos && left[k-i] <= n-1-pos) {
// cout << pos << " " << right[i] << " " << left[k-i] << "\n";
white[pos] = true;
}
if (i == k) continue;
for (int shift = 0; shift < c[i]; shift++) {
if (count(s.begin()+pos-shift,s.begin()+pos-shift+c[i],'_') == 0 && (i == 0 || right[i] <= pos-shift-1) && (i == k-1 || left[k-1-i] <= n-(pos-shift+c[i]+1)) && (pos-shift >= 0) && (pos-shift+c[i]-1 < n)) {
assert(s[pos] != '_');
// cout << pos << " " << i << " " << shift << "\n";
black[pos] = true;
}
}
}
}
string ans = s;
for (int pos = 0; pos < n; pos++) {
assert(white[pos] || black[pos]);
if (white[pos] && black[pos]) ans[pos] = '?';
else if (white[pos]) ans[pos] = '_';
else if (black[pos]) ans[pos] = 'X';
}
return ans;
}
