#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int N = 2e5+1, K = 101, oo = 1e9;
string solve_puzzle(string s, vector<int> c) {
s = '_'+s+'_';
int n = s.size(), k = c.size();
vi prefW(n+1);
auto good = [&](int st, int id) {
// check if we can place block c[id] at place st
int e = st+c[id];
if(e>=n) return false;
if(prefW[e]-prefW[st]!=0) return false;
if(s[e]=='X') return false;
if(s[st-1]=='X') return false;
return true;
};
// compute prefcan and sufcan
vector<vector<bool>> pref,suf;
for(int rep=0;rep<2;++rep) {
reverse(all(s));
reverse(all(c));
swap(pref,suf);
for(auto& b : suf) {
for(int i=0;i<=k/2;++i) {
swap(b[i],b[k-i]);
}
}
reverse(all(suf));
fill(all(prefW),0);
for(int i=0;i<n;++i) {
prefW[i+1] = prefW[i]+(s[i]=='_');
}
pref.assign(n,vector<bool>(k+1));
pref[0][0]=1;
for(int i=1;i<n;++i) {
for(int j=0;j<=k;++j) {
pref[i][j] = pref[i][j] or (pref[i-1][j] and s[i-1]!='X');
if(!pref[i][j] or j==k) continue;
if(good(i,j)) {
int to = i+c[j]+1;
if(to<n) pref[to][j+1] = true;
}
}
}
}
// calculate answer
string res(n,'?');
vi p(n+1);
// handle blacks
for(int j=0;j<k;++j) {
int l = c[j];
for(int i=1;i+l<n;++i) if( good(i,j)) {
if(pref[i][j] and suf[i+l-1][j+1]) {
p[i]++,p[i+l]--;
}
}
}
partial_sum(all(p),p.begin());
for(int i=0;i<n;++i) {
if(!p[i]) res[i]='_';
}
// handle whites
for(int i=1;i<n-1;++i) {
if(res[i]=='?') {
bool g= false;
// not in b
for(int j=0;j<=k and !g;++j) {
if(pref[i+1][j] and suf[i-1][j]) {
g=true;
}
}
if(!g) res[i]='X';
}
}
return res.substr(1,n-2);
}
