#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10 , K = 110;
int n , pw[N] , pb[N] , k;
bool dp[N][K] , reach[N][K] , W[N] , B[N];
string s;
bool can(int id , int bl)
{
if(id + bl > n)
return false;
int tmp = pw[id + bl - 1];
if(id > 0)
tmp -= pw[id - 1];
if(tmp != 0)
return false;
if(id + bl < n && s[id + bl] == 'X')
return false;
return true;
}
string solve_puzzle(string ss, vector<int> c) {
n = ss.size();
k = c.size();
s = ss;
dp[n][k] = true;
pw[0] = (s[0] == '_' ? 1 : 0);
pb[0] = (s[0] == 'X' ? 1 : 0);
for(int i = 1 ; i < n ; i++)
{
pw[i] = pw[i - 1];
pb[i] = pb[i - 1];
pw[i] += (s[i] == '_' ? 1 : 0);
pb[i] += (s[i] == 'X' ? 1 : 0);
}
for(int i = n - 1 ; i >= 0 ; i--)
{
if(s[i] != 'X')
dp[i][k] = dp[i + 1][k];
for(int j = 0 ; j < k ; j++)
{
if(s[i] != 'X')
dp[i][j] = dp[i + 1][j];
if(can(i , c[j]))
dp[i][j] |= dp[min(n , i + c[j] + 1)][j + 1];
}
}
reach[0][0] = true;
int las = -1;
for(int i = 0 ; i < n ; i++)
{
if(las >= i)
B[i] = true;
for(int j = 0 ; j <= k ; j++) if(reach[i][j])
{
//cout << i << " : " << j << endl;
if(dp[i + 1][j] && s[i] != 'X')
{
W[i] = true;
reach[i + 1][j] = true;
}
if(j != k && dp[min(i + c[j] + 1 , n)][j + 1] && can(i , c[j]))
{
B[i] = true;
W[i + c[j]] = true;
reach[min(i + c[j] + 1 , n)][j + 1] = true;
las = max(las , i + c[j] - 1);
}
}
if(!W[i])
s[i] = 'X';
else if(!B[i])
s[i] = '_';
else
s[i] = '?';
}
return s;
}
