#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n, k, isblack[200010], iswhite[200010], mxwhite[200010], mxblack[200010], cblack[200010], cwhite[200010], clues[200010];
bool done[200010][110];
int memo[200010][110];
int dp(int a, int b)
{
// printf("%d %d\n", a, b);
if (a >= n && b != k) return 0;
if (a >= n && b == k) return 1;
if (b == k)
{
int w = cblack[n-1];
if (a) w -= cblack[a-1];
if (!w)
{
mxwhite[a] = max(mxwhite[a], n);
}
// printf("%d %d %d\n", a, b, !w);
return !w;
}
if (done[a][b]) return memo[a][b];
done[a][b] = 1;
int sz = clues[b];
int poss = 0;
if (!isblack[a]) poss = dp(a+1, b);
if (poss) mxwhite[a] = max(mxwhite[a], 1);
if (a + sz > n) return memo[a][b] = poss;
int w = cwhite[a+sz-1];
if (a) w -= cwhite[a-1];
if (w) return memo[a][b] = poss;
if (isblack[a+sz]) return memo[a][b] = poss;
// printf(" ab %d %d\n", a, b);
if (!dp(a+sz+1, b+1)) return memo[a][b] = poss;
// printf("ab %d %d\n", a, b);
poss = 1;
mxblack[a] = max(mxblack[a], sz);
mxwhite[a+sz] = max(mxwhite[a+sz], 1);
return memo[a][b] = poss;
}
string solve_puzzle(string s, vector<int> c) {
n = s.size();
k = c.size();
for (int i = 0; i < k; i++) clues[i] = c[i];
for (int i = 0; i < n; i++)
{
if (s[i] == 'X') isblack[i] = 1;
if (s[i] == '_') iswhite[i] = 1;
if (i) cblack[i] = cblack[i-1];
if (i) cwhite[i] = cwhite[i-1];
cwhite[i] += iswhite[i];
cblack[i] += isblack[i];
}
int poss = dp(0, 0);
priority_queue<int> pq;
for (int i = 0; i < n; i++)
{
// printf("%d : %d\n", i, mxwhite[i]);
pq.push(-(i + mxwhite[i]));
while (!pq.empty() && -pq.top() <= i) { pq.pop(); }
if (pq.size()) iswhite[i] = 1;
}
while (pq.size()) pq.pop();
for (int i = 0; i < n; i++)
{
// printf("%d : %d\n", i, mxblack[i]);
pq.push(-(i + mxblack[i]));
while (!pq.empty() && -pq.top() <= i) { pq.pop(); }
if (pq.size()) isblack[i] = 1;
}
string ans;
for (int i = 0; i < n; i++)
{
// printf("%d %d\n", iswhite[i], isblack[i]);
if (iswhite[i] && isblack[i]) ans.push_back('?');
else if (iswhite[i]) ans.push_back('_');
else if (isblack[i]) ans.push_back('X');
// else assert(false);
}
return ans;
}
