#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n = s.length(), k = c.size();
s = "@"+s+"@";
vector<int> pref(n+2, 0);
vector<vector<int>> dpl(n+2, vector<int>(k+1, 0)), dpr(n+2, vector<int>(k+1, 0));
for (int i = 1; i <= n+1; i++) {
pref[i] = pref[i-1];
if (s[i] == '_') {
pref[i]++;
}
}
dpl[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (s[i] != 'X') {
dpl[i][j] |= dpl[i-1][j];
}
if (j > 0 && i-c[j-1] >= 0 && pref[i]-pref[i-c[j-1]] == 0 && (i-c[j-1] <= 0 || s[i-c[j-1]] != 'X')) {
dpl[i][j] |= dpl[max(0, i-c[j-1]-1)][j-1];
}
}
}
reverse(c.begin(), c.end());
dpr[n+1][0] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= k; j++) {
if (s[i] != 'X') {
dpr[i][j] |= dpr[i+1][j];
}
if (j > 0 && i+c[j-1] <= n+1 && pref[i+c[j-1]-1]-pref[i-1] == 0 && (i+c[j-1] > n || s[i+c[j-1]] != 'X')) {
dpr[i][j] |= dpr[min(n+1, i+c[j-1]+1)][j-1];
}
}
}
//for (int i = 1; i < n+2; i++) {
// for (int j = 0; j <= k; j++) {
// cout << dpl[i][j] << " ";
// }
// cout << endl;
//}
//cout << endl;
//for (int i = 1; i < n+2; i++) {
// for (int j = 0; j <= k; j++) {
// cout << dpr[i][j] << " ";
// }
// cout << endl;
//}
vector<pair<int, int>> ans(n+2, {0, 0});
for (int i = 1; i <= n; i++) {
if (s[i] == 'X') {
continue;
}
for (int j = 0; j <= k; j++) {
int kr = k-j;
if (dpl[i-1][j] && dpr[i+1][kr]) {
ans[i].first = 1;
}
}
}
reverse(c.begin(), c.end());
for (int i = 1; i <= n; i++) {
if (s[i] == '_') {
continue;
}
if (s[i] == 'X') {
ans[i].second = 1;
continue;
}
for (int j = 0; j <= k; j++) {
int kr = k-j;
if (!dpr[min(n+1, i+2)][kr] || (i+1 <= n && s[i+1] == 'X')) {
continue;
}
if (j > 0 && i-c[j-1] >= 0 && pref[i]-pref[i-c[j-1]] == 0 && (i-c[j-1] <= 0 || s[i-c[j-1]] != 'X') && dpl[max(0, i-c[j-1]-1)][j-1]) {
for (int l = i-c[j-1]+1; l <= i; l++) {
ans[l].second = 1;
}
}
}
}
reverse(c.begin(), c.end());
for (int i = 0; i >= 1; i--) {
if (s[i] == '_') {
continue;
}
if (s[i] == 'X') {
ans[i].second = 1;
continue;
}
for (int j = 0; j <= k; j++) {
int kl = k-j;
if (!dpl[max(0, i-2)][kl] || (i-1 >= 1 && s[i-1] == 'X')) {
continue;
}
if (j > 0 && i+c[j-1] <= n+1 && pref[i+c[j-1]-1]-pref[i-1] == 0 && (i+c[j-1] > n || s[i+c[j-1]] != 'X') && dpr[min(n+1, i+c[j-1]+1)][j-1]) {
dpr[i][j] |= dpr[min(n+1, i+c[j-1]+1)][j-1];
}
}
}
string res = "";
for (int i = 1; i <= n; i++) {
if (ans[i].first && ans[i].second) {
res.push_back('?');
} else if (ans[i].first) {
res.push_back('_');
} else if (ans[i].second) {
res.push_back('X');
} else {
res.push_back('X');
}
}
return res;
}
