#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10, K=210;
int f1[N][K], f2[N][K], n, k, nxt[N];
string solve_puzzle(string s, vector<int> c) {
n=s.size(), k=c.size();
s=" "+s; c.insert(c.begin(), 0);
nxt[n+1]=n+1;
for (int i=n; i>=1; --i){
if (s[i]=='_') nxt[i]=i;
else nxt[i]=nxt[i+1];
}
f1[0][0]=f1[0][1]=1;
for (int i=1; i<=n; ++i){
for (int j=1; j<=k*2+1; ++j){
if (j&1){
if (s[i]!='X'){
f1[i][j]|=f1[i-1][j];
f1[i][j]|=f1[i-1][j-1];
}
}else{
int len=c[j>>1];
if (i>=len && nxt[i-len+1]>i){
f1[i][j]|=f1[i-len][j-1];
}
}
}
}
f2[n+1][k*2+1]=1; f2[n+1][k*2+2]=1;
for (int i=n; i>=1; --i){
for (int j=1; j<=k*2+1; ++j){
if (j&1){
if (s[i]!='X'){
f2[i][j]|=f2[i+1][j];
f2[i][j]|=f2[i+1][j+1];
}
}else{
int len=c[j>>1];
if (i+len-1<=n && nxt[i]>i+len-1){
f2[i][j]|=f2[i+len][j+1];
}
}
}
}
string ans(n, '?');
vector<int> d(n+1), check0(n+1), check1(n+1);
for (int i=1; i<=n; ++i){
for (int j=1; j<=k*2+1; ++j){
if (j&1){
if (f1[i][j] && (f2[i+1][j] || f2[i+1][j+1])){
check0[i]=1;
}
}else{
int len=c[j>>1];
if (f1[i][j] && f2[i+1][j+1]){
int l=i-len+1, r=i;
++d[l];
if (r<n) --d[r+1];
}
}
}
}
partial_sum(d.begin(), d.end(), check1.begin());
for (int i=1; i<=n; ++i){
if (check0[i] && !check1[i]) ans[i-1]='_';
if (check1[i] && !check0[i]) ans[i-1]='X';
}
return ans;
}
