#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
bool can(std::string s, int tam, int pos){
bool ret = true;
if(pos - tam + 1 < 0) return false;
for(int i = pos - tam + 1; i <= pos; i++)
ret &= s[i] != '_';
return ret;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size();
int k = c.size();
vector<int> l(k, 0), r(k, 0);
vector<bool> w(n, false), b(n, false);
int fim = 0;
for(int i = 0; i < k; i++){
fim += c[i] - 1;
while(!can(s, c[i], fim)) fim++;
l[i] = fim;
fim += 2;
// printf("%d ", l[i]);
}
// printf("\n");
fim = n - 1;
for(int i = k - 1; i >= 0; i--){
while(!can(s, c[i], fim)) fim--;
r[i] = fim;
fim -= 1 + c[i];
}
// for(int i = 0; i < k; i++)
// printf("%d ", r[i]);
// printf("\n");
vector<int> pb(n, INF);
for(int i = 0; i < k; i++){
int left = l[i] - c[i] + 1;
int right = r[i];
for(int j = left; j <= right; j++)
pb[j] = min(pb[j], c[i]);
}
for(int i = 0; i < n; i++){
if(s[i] == 'X') continue;
int id = lower_bound(l.begin(), l.end(), i) - l.begin() - 1;
// printf("k[%d] = %d\n", i, id);
if(s[i] == '_' || id == k - 1 || r[id + 1] - c[id + 1] + 1 > i) w[i] = true;
else w[i] = false;
}
for(int i = 0; i < n; i++){
if(s[i] == 'X') {
b[i] = true;
continue;
}
if(s[i] == '_') continue;
int tam = pb[i];
if(tam == INF) {
b[i] = false;
continue;
}
bool flag = false;
for(int j = 0; j < tam; j++)
flag |= can(s, tam, i + j);
b[i] = flag;
}
string ans(n, '?');
for(int i = 0; i < n; i++){
// printf("%d %d %d\n", i, b[i] ? 1 : 0, w[i] ? 1 : 0);
if(!b[i]) ans[i] = '_';
if(!w[i]) ans[i] = 'X';
}
return ans;
}
