#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int N, K; tuple<int, int, int> pre[200009][109][2]; int t[200009][3];
bool dp[200009][109][2]; char cc[200009];
int ranged(int l, int r, int x) {
return t[r][x] - t[l - 1][x];
}
string solve_puzzle(string s, vector<int> c) {
N = s.size(); K = c.size();
for (int i = 0; i < N; i++) {
if (s[i] == 'X') t[i + 1][0]++;
if (s[i] == '_') t[i + 1][1]++;
if (s[i] == '?') t[i + 1][2]++;
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 3; j++) t[i][j] += t[i - 1][j];
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
for (int k = 0; k < 3; k++) pre[i][j][k] = make_tuple(-1, -1, -1);
}
}
dp[0][0][0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
int pres = -1, pre2 = -1;
if (i >= 1 && ranged(i, i, 0) == 0) {
if (dp[i - 1][j][0] == true) { pres = j; pre2 = 0; }
else if (dp[i - 1][j][1] == true) { pres = j; pre2 = 1; }
}
if (pres >= 0) {
pre[i][j][0] = make_tuple(i - 1, pres, pre2); dp[i][j][0] = true;
}
pres = -1; pre2 = -1;
if (j >= 1 && i >= c[j - 1] && ranged(i - c[j - 1] + 1, i, 1) == 0) {
if (dp[i - c[j - 1]][j - 1][0] == true) { pres = j - 1; pre2 = 0; }
}
if (pres >= 0) {
pre[i][j][1] = make_tuple(i - c[j - 1], pres, pre2); dp[i][j][1] = true;
}
}
}
for (int i = 1; i <= N; i++) cc[i] = '_';
int cx = N, cy = K, cz = 0; if (dp[N][K][0] == false) cz = 1;
while (cx >= 1) {
int v1 = get<0>(pre[cx][cy][cz]), v2 = get<1>(pre[cx][cy][cz]), v3 = get<2>(pre[cx][cy][cz]);
//cout << cx << " " << cy << " " << cz << " " << v1 << " " << v2 << " " << v3 << endl;
if (cz == 1) {
for (int i = v1 + 1; i <= cx; i++) cc[i] = 'X';
}
cx = v1; cy = v2; cz = v3;
}
string str = "";
for (int i = 1; i <= N; i++) str += cc[i];
return str;
}
