#include <bits/stdc++.h>
#include "paint.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int mod = 1e9 + 7;
string solve_puzzle(string s, vector<int> c) {
int n = s.size(); int k = c.size();
c.push_back(0);
for (int i = k; i >= 1; i--) c[i] = c[i - 1];
s = "1" + s;
vector<int> pref(n + 1);
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (s[i] == '_');
vector<vector<int>> dp1(n + 1, vector<int>(k + 1));
dp1[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (s[i] != 'X') dp1[i][j] |= dp1[i - 1][j];
int pi = i - c[j] - 1;
if (pi >= 0 && j >= 1 && s[i] != 'X' && pref[i - 1] == pref[pi]) dp1[i][j] |= dp1[pi][j - 1];
}
}
vector<vector<int>> dp2(n + 2, vector<int>(k + 2));
dp2[n + 1][k + 1] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= k + 1; j++) {
if (s[i] != 'X') dp2[i][j] |= dp2[i + 1][j];
int pi = i + c[j] + 1;
if (pi <= n + 1 && j <= k && s[i] != 'X' && pref[i] == pref[pi - 1]) dp2[i][j] |= dp2[pi][j + 1];
}
}
vector<int> dp3(n + 2);
for (int i = 1; i <= n; i++) {
int w = 0;
for (int j = 0; j <= k; j++) {
if (dp1[i][j] && dp2[i][j + 1]) w = 1;
if (j == 0 || i + c[j] > n + 1) continue;
if (dp1[i - 1][j - 1] && dp2[i + c[j]][j + 1] && pref[i - 1] == pref[i + c[j] - 1]) {
dp3[i]++;
dp3[i + c[j]]--;
}
}
dp3[i] += dp3[i - 1];
if (w && dp3[i]) s[i] = '?';
else if (w) s[i] = '_';
else s[i] = 'X';
}
string ret;
for (int i = 1; i <= n; i++) ret += s[i];
return ret;
}
