#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
void r(bool &a, bool b){ a = a || b; }
const int LIM = 2e5;
bool dp[2][LIM+2][101];
int n, k;
string solve_puzzle(string s, vector<int> c){
n = s.size(), k = c.size();
c.insert(c.begin(), 0);
s.insert(s.begin(), 0);
int a[n+1] = {0};
for(int h=0; h<2; ++h){
for(int i=0; i<=n; ++i) fill(dp[h][i], dp[h][i]+101, 0);
reverse(c.begin()+1, c.end());
reverse(s.begin()+1, s.end());
for(int i=1; i<=n; ++i) a[i] = (s[i] == '_') + a[i-1];
dp[h][0][0] = 1;
for(int i=1; i<=n; ++i){
if(s[i] != 'X') for(int j=0; j<=k; ++j) dp[h][i][j] = dp[h][i-1][j];
for(int j=1; j<=k; ++j){
if(i < c[j] || a[i] - a[i-c[j]]) continue;
if(j < 2) r(dp[h][i][j], dp[h][i-c[j]][j-1]);
if(j > 1) r(dp[h][i][j], i > c[j] && s[i-c[j]] != 'X' && dp[h][i-c[j]-1][j-1]);
}
}
}
bool possible[n+1];
for(int i=1; i<n; ++i){
possible[i] = 0;
for(int j=0; j<=k; ++j){
if(dp[1][i-1][j] && dp[0][n-i][k-j] && s[i] != 'X') possible[i] = 1;
}
}
possible[n] = dp[1][n-1][k] && s[n] != 'X';
vector<int> pre(n+2);
s.push_back('.');
for(int i=1; i<=n; ++i){
for(int j=1; j<=k; ++j){
if(i < c[j] || a[i] - a[i-c[j]]) continue;
if(dp[1][max(0, i-c[j]-1)][j-1] && s[i-c[j]] != 'X' && s[i+1] != 'X' && dp[0][max(0, n-i-1)][k-j]) ++pre[i-c[j]+1], --pre[i+1];
}
}
string res(n, '?');
for(int i=1; i<=n; ++i){
pre[i] += pre[i-1];
if(!pre[i]) res[i-1] = '_';
if(!possible[i]) res[i-1] = 'X';
}
return res;
}
