#include "paint.h"
#include <cstdlib>
#include <vector>
#include <assert.h>
#include <iostream>
using namespace std;
string S;
int N, K, C[200001];
int pref[200001], kp[200001];
bool DP[101][200001];
bool trav[101][200001];
bool ans[200001][2];
void backtrack(int k, int n)
{
if (!trav[k][n])
{
//cout << "BKTRK " << k << " " << n << "\n";
trav[k][n] = 1;
if (n && S[n - 1] != 'X' && DP[k][n - 1])
{
ans[n - 1][1] = 1;
backtrack(k, n - 1);
}
if (k && n >= C[k - 1] + (k > 1) && pref[n] == pref[n - C[k - 1]] && ((k == 1) || S[n - C[k - 1] - 1] != 'X') && DP[k - 1][n - C[k - 1] - (k > 1)])
{
if (k > 1) ans[n - C[k - 1] - 1][1] = 1;
kp[n - C[k - 1]] = max(kp[n - C[k - 1]], C[k - 1]);
backtrack(k - 1, n - C[k - 1] - (k > 1));
}
}
}
string solve_puzzle(string s, vector<int> c)
{
N = s.size(); K = c.size();
S = s;
for (int i = 0; i < K; i++) {C[i] = c[i];}
for (int i = 1; i <= N; i++) {pref[i] = pref[i - 1] + (s[i - 1] == '_');}
DP[0][0] = 1;
for (int j = 1; j <= N && s[j - 1] != 'X'; j++) {DP[0][j] = 1;}
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= N; j++)
{
if (s[j - 1] != 'X') DP[i][j] |= DP[i][j - 1];
if (j >= c[i - 1] + (i > 1) && pref[j] == pref[j - c[i - 1]] && ((i == 1) || s[j - c[i - 1] - 1] != 'X'))
{
DP[i][j] |= DP[i - 1][j - c[i - 1] - (i > 1)];
}
//cout << i << " " << j << " " << DP[i][j] << "\n";
}
}
assert(DP[K][N]);
backtrack(K, N);
int cur = 0;
for (int i = 0; i < N; i++)
{
//cout << kp[i] << "\n";
if (kp[i]) {cur = max(cur, kp[i] + i);}
ans[i][0] = (i < cur);
}
string ret = "";
for (int i = 0; i < N; i++)
{
if (ans[i][0] && ans[i][1]) {ret.push_back('?');}
else if (ans[i][0]) {ret.push_back('X');}
else {ret.push_back('_');}
}
return ret;
}
