#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;
vector<int> c;
bool can(int i, int j, bool l, bool r)
{
int len = c[j];
if (i < 0)
return 0;
if (i + len > n)
return 0;
if (next_[i] < i + len)
return 0;
if (l && i != 0 && isx[i-1])
return 0;
if (r && i + len != n && isx[i + len])
return 0;
return 1;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
::c = c;
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] = !isx[i-1] && dp1[i-1][0];
Loop (j,0,k) {
dp1[i][j+1] |= can(i-c[j], j, 1, 0) && dp1[i - c[j] - (i-c[j]>0)][j];
dp1[i][j+1] |= !isx[i-1] && dp1[i-1][j+1];
}
}
dp2[n][k] = 1;
LoopR (i,0,n) {
dp2[i][k] = !isx[i] && dp2[i+1][k];
Loop (j,0,k) {
dp2[i][j] |= can(i, j, 0, 1) && dp2[i + c[j] + (i+c[j]<n)][j+1];
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 = can(i, j, 1, 1) && dp1[i - (i>0)][j] && dp2[i + c[j] + (i+c[j]<n)][j+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;
}
