#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
const int maxk = 1e2 + 20;
string s;
int dp[maxn][maxk];
int c[maxk] , nw[maxn] , can[maxn][2];
bool visited[maxn][maxk];
// 0 -> white
void dfs(int n , int k)
{
if(n <= 0 || !dp[n][k] || visited[n][k])
return;
visited[n][k] = 1;
if(s[n] == 'X')
{
can[n - c[k - 1]][0]++;
can[n - c[k - 1] + 1][0]--;
can[n - c[k - 1] + 1][1]++;
can[n + 1][1]--;
dfs(n - c[k - 1] - 1 , k - 1);
}
else if(s[n] == '_')
{
can[n][0]++;
can[n + 1][0]--;
dfs(n - 1 , k);
}
else
{
int cnt = 0;
if(k && n >= c[k - 1] && nw[n] - nw[n - c[k - 1]] == 0 && s[n - c[k - 1]] != 'X')
{
bool is = (n == c[k - 1]? k == 1 : dp[n - c[k - 1] - 1][k - 1] != 0);
if(is)
{
can[n - c[k - 1]][0]++;
can[n - c[k - 1] + 1][0]--;
can[n - c[k - 1] + 1][1]++;
can[n + 1][1]--;
dfs(n - c[k - 1] - 1 , k - 1);
}
}
if(dp[n - 1][k] != 0)
{
cnt++;
can[n][0]++;
can[n + 1][0]--;
dfs(n - 1 , k);
}
}
}
string solve_puzzle(string S, vector<int> C)
{
s = S;
int n = s.size() , k = C.size();
for(int i = 0; i < k; i++)
c[i] = C[i];
s = '_' + s;
for(int i = 1; i <= n; i++)
nw[i] = nw[i - 1] + (s[i] == '_');
dp[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++)
{
if(s[i] == 'X')
{
if(j && i >= c[j - 1] && nw[i] - nw[i - c[j - 1]] == 0 && s[i - c[j - 1]] != 'X')
dp[i][j] = (i == c[j - 1]? j == 1 : dp[i - c[j - 1] - 1][j - 1] != 0);
}
else if(s[i] == '_')
dp[i][j] = (dp[i - 1][j] != 0);
else
{
if(j && i >= c[j - 1] && nw[i] - nw[i - c[j - 1]] == 0 && s[i - c[j - 1]] != 'X')
dp[i][j] += (i == c[j - 1]? j == 1 : dp[i - c[j - 1] - 1][j - 1] != 0);
dp[i][j] += (dp[i - 1][j] != 0);
}
}
dfs(n , k);
string res;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < 2; j++)
can[i][j] += can[i - 1][j];
if(!can[i][0] && !can[i][1])
res += '?';
else if(can[i][0] && can[i][1])
res += '?';
else if(can[i][0])
res += '_';
else
res += 'X';
}
return res;
}
