#include "paint.h"
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 5005
using namespace std;
int n, m, c[N], v[N][N][2], ans[N][2], ss[N];
string a;
int f(int p, int q, int w, int z) {
int t, ch = 0;
if (v[p][q][z] != -1) return v[p][q][z];
if (p == 7 && q == 3 && z == 0) {
t = 0;
}
if (p == n) {
if (w == m + 1) return 1;
return 0;
}
if (z == 0 && (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, 0);
if (t == 1) {
ans[p][1] = 1;
ch = 1;
}
}
return v[p][q][z] = ch;
}
std::string solve_puzzle(std::string s, std::vector<int> cc) {
int i;
a = s;
n = a.size();
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, 1, 0);
for (i = 0;i < n; i++) {
if (ans[i][0] + ans[i][1] == 2) {
a[i] = '?';
} else if (ans[i][0] + ans[i][1] == 1) {
if (ans[i][0] == 1) a[i] = 'X';
else a[i] = '_';
} else a[i] = '?';
}
return a;
}
