#include "paint.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 200010;
const int K = 110;
int next_[N];
bool isx[N];
bool dp1[N][K], dp2[N][K];
int canx[N];
int can_[N];
int n, k;
std::string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
next_[n] = N;
LoopR (i,0,n) {
next_[i] = s[i] == '_'? i: next_[i+1];
isx[i] = s[i] == 'x' || s[i] == 'X';
}
dp1[0][0] = 1;
Loop (i,1,n+1) {
dp1[i][0] = s[i-1] != 'X' && dp1[i-1][0];
Loop (j,0,k) {
dp1[i][j+1] |= i >= c[j] && ((i-c[j]==0&&j==0) || dp1[i-c[j]-1][j]) && !isx[i] && next_[i-c[j]] >= i;
dp1[i][j+1] |= !isx[i-1] && dp1[i-1][j+1];
}
}
dp2[n][k] = 1;
LoopR (i,0,n) {
dp2[i][k] = s[i] != 'X' && dp2[i+1][k];
Loop (j,0,k) {
dp2[i][j] |= i+c[j] <= n && ((i+c[j]==n&&j+1==k) || dp2[i+c[j]+1][j+1]) && !isx[i+c[j]] && next_[i] >= i+c[j];
dp2[i][j] |= !isx[i] && dp2[i+1][j];
}
}
Loop (i,0,n)
Loop (j,0,k+1)
can_[i] |= dp1[i][j] && dp2[i+1][j] && !isx[i];
Loop (j,0,k) {
Loop (i,0,n-c[j]+1) {
int tmp = ((i==0&&j==0) || dp1[i-1][j])
&& ((i+c[j]==n&&j==k-1) || dp2[i+c[j]+1][j+1])
&& next_[i] >= i+c[j]
&& !isx[i+c[j]] && (i==0||!isx[i-1]);
canx[i ] += tmp;
canx[i+c[j]] -= tmp;
}
}
Loop (i,0,n)
canx[i+1] += canx[i];
string ans(n, '.');
Loop (i,0,n) {
if (canx[i] && can_[i]) s[i] = '?';
else if (canx[i] ) s[i] = 'X';
else if ( can_[i]) s[i] = '_';
else assert(false);
}
return s;
}
