#include "paint.h"
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 200005
using namespace std;
int n, m, c[N], v[N][105], ans[N][2], ss[N], cnt[N], mx[N];
string a;
int g(int p) {
if (p < 0) return 0;
return cnt[p];
}
int f(int p, int q) {
int t, ch = 0, cch = 0, pl;
if (p >= n) {
if (q == m) return 1;
return 0;
}
if (v[p][q] != -1) return v[p][q];
pl = c[q + 1];
if (q < m && p + pl - 1 < n && g(p + pl - 1) - g(p - 1) == 0 && a[p + pl] != 'X') {
t = f(p + pl + 1, q + 1);
if (t == 1) {
ans[p + pl][1] = 1;
ans[p][0] = 1;
cch = 1;
}
}
if (a[p] == '.' || a[p] == '_') {
t = f(p + 1, q);
if (t == 1) {
ans[p][1] = 1;
ch = 1;
}
}
if (cch) {
mx[p] = max(mx[p], p + pl - 1);
}
// if ((a[p] == '.' || a[p] == 'X')) {
// if (q + 1 < ss[w]) t = f(p + 1, q + 1, w, 0);
// else t = f(p + 1, q + 1, w + 1, 1);
// if (t == 1) {
// ans[p][0] = 1;
// ch = 1;
// }
// }
// if ((a[p] == '.' || a[p] == '_') && !(z == 0 && q > ss[w - 1] && q < ss[w])) {
// t = f(p + 1, q, w);
// if (t == 1) {
// ans[p][1] = 1;
// ch = 1;
// }
// }
return v[p][q] = (ch | cch);
}
std::string solve_puzzle(std::string s, std::vector<int> cc) {
int i, la;
a = s;
n = a.size();
// cout << n << endl;
if (a[0] == '_') cnt[0] = 1;
else cnt[0] = 0;
for (i = 1; i < n; i++) cnt[i] = cnt[i - 1] + (a[i] == '_');
cnt[n] = cnt[n - 1];
m = cc.size();
for (i = 0; i < m; i++) {
c[i + 1] = cc[i];
}
for (i = 1; i <= m; i++) ss[i] = ss[i - 1] + c[i];
memset(v, -1, sizeof(v));
f(0, 0);
la = -1;
bool vb, vw;
for (i = 0; i < n; i++) {
vb = vw = 0;
if (ans[i][0]) la = max(la, mx[i]);
if (ans[i][0]) vb = 1;
if (la != -1 && i <= la) vb = 1;
if (ans[i][1]) vw = 1;
if (vb + vw == 2) {
a[i] = '?';
} else if (vb + vw == 1) {
if (vb == 1) a[i] = 'X';
else a[i] = '_';
} else a[i] = '?';
}
return a;
}
